< Back to forum

Can someone explain the approach to this question

Prime Path - SPOJ. The tag to question says BFS but how to use BFS in this question?

spoj graph

Asked by: Rishabh_Sethi on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.

Enter your answer details below:


Enter your comment details below:




1 Answer(s)

Well, as the questions says, you gotta find the minimum no of ways the transformation can be done in, you basically need to go through each step of transformation which can be realised by a breadth-first-traversal. 

Use a 

 

queue < pair<int, int> > myQueue;

 

to keep track of room number and their tranform level. The initial room number will have a tranform_level of 0.

Take the input, transform one of its digit, check for prime, increment the transform_level by 1 for the modified room number and enqueue. All possible configurations of the room number will be present in the Queue until you find the destination room number. Since it's a BFS, you wont need to keep track of the best transformation. The Algorithm will take care of it. Now, after a few iterations, if you dequeue the queue and get the result, the transform_level associated with that dequeued string would give you the answer. 

Shashank_Shekhar last updated on April 7, 2019, 6:34 p.m. 0    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.