12101 - Prime Path
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. |
||||||||||
12101 - Prime Path