PPATH

Prime Path

Link to the question : PPATH

RECOMMENDED QUESTION:

Try your hands on this permutation question : QUESTION

HINT :

A good problem on bfs for beginners. The question asks us to find the shortest route between the two prime numbers. What we can do is change each digit of the number and check whether the new number is prime. If its prime then we again apply the above process and continue this process untill we reach the destination. 

The forming of new number and traversing to new one can be easily done  using Breadth First Search. If you don't know about it, I would recommend you to have a look at it here .

SOLUTION :

#include<bits/stdc++.h>



using namespace std;




bool prime[100005];

 bool visit[100005];

int dist[100005];




void sieve(int n = 100005)

{

    // Create a boolean array "prime[0..n]" and initialize

    // all entries it as true. A value in prime[i] will

    // finally be false if i is Not a prime, else true.

    

    memset(prime, true, sizeof(prime));

    prime[0] = false;

    prime[1] = false;

    for (int p=2; p*p<=n; p++)

    {

        // If prime[p] is not changed, then it is a prime

        if (prime[p] == true)

        {

            // Update all multiples of p

            for (int i=p*p; i<=n; i += p)

                prime[i] = false;

        }

    }

 

    

}

int conv_to_num(int a[])

{

 int n;

 n = (a[3] *1000)  + (a[2] *100)   + (a[1] * 10) + (a[0]);

 return n;

}




void conv_to_arr(int digit[],int n)

{

 digit[0] = n%10;

 n /= 10;

    digit[1] = n%10;

 n /= 10;

 digit[2] = n%10;

 n /= 10;

 digit[3] = n%10;

  

}

int main()

{

 int t;

 sieve();

 

 scanf("%d",&t);

 

 while(t--)

 {

      queue<int> q;

  int num1, num2,  i, digit[4];

  scanf("%d%d",&num1,&num2);

  memset(dist,-1,sizeof(dist));

  memset(visit,false,sizeof(visit));

  if(num1 == num2)

  {

   printf("0\n");

   continue;

  }

  q.push(num1);

     dist[num1] = 0;

     visit[num1] = true;

     //printf("hello\n");    //chedk

  while(!q.empty())

  {

           //printf("hello\n");    //chedk

        int val = q.front();

       // cout<<"val = "<<val<<endl;    //check

        if(val == num2)

        break;

       // q.pop();

       // conv_to_arr(val);

        //cout<<digit[3]<<digit[2]<<digit[1]<<digit[0]<<endl;

        for(i= 0; i<4; i++)

        {

             //int x = digit[i];

             conv_to_arr(digit,val);

                for(int j= 0; j<10; j++)

       {

            

               digit[i] = j;

         int temp = conv_to_num(digit);

         if(!visit[temp] && prime[temp] && temp >= 1000) 

         {

              //printf("hello\n");    //chedk

              //cout<<"temp = "<<temp<<endl;   //check

               visit[temp] = true;

               q.push(temp);

               dist[temp] =  dist[val] + 1;

             }  

       } 

      // digit[i] = x;

       //cout<<digit[3]<<digit[2]<<digit[1]<<digit[0]<<endl;

     }

     q.pop();

  } 

  if(dist[num2]==-1)

  printf("-1\n");

  else

  printf("%d\n",dist[num2]);

  //cout<<prime[3739]<<endl;

 }

 return 0;

}