# UVA Problem: 12101 (Prime Path )

October 5, 2011

**Problem Explanation:**

This is a simple BFS problem . There is nothing special to mention for this problem.

1. First generate prime number upto 9999.

2. Then just run BFS from the initial number. Like if the number is 1033 where else we can go

2.a Changing the first digit we get 8 number (2-9)033, changing second digit we get 9 number 1(1-9)33 and so on. If any of the number is prime then place it in queue and mark this as visited so that you don’t push it again.

3. Push and Pop the numbers until you get the desired number. If number not found print “

Impossible.” else print the distance.

Advertisements

No comments yet