12101 - Prime Path

Difficulty : medium

Solution Description :

Graph BFS Problem

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. Changing the first digit we get 9 number (1-9)033, changing second digit we get 10 number 1(0-9)33, third digit we get 10 number 10(0-9)3 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.
i.e. the adjacency of a node are change 1st, 2nd, 3rd, and 4th digit (0-9)(0-9)(0-9)(0-9) if the new number is a prime number and is greater than 999.
3.  Push and Pop the numbers until you get the desired number. If number not found print “Impossible” else print the distance.

4. If you find the desired number then print shortest path length.

5. In this input data set no input which output is Impossible.