QUEEN

Wandering Queen

Link to the question : QUEEN

HINT :

This question requires bfs as can be clearly understood from the tag. We start doing bfs from the position of the queen. And push into the queue all the squares which can be visited by the queen from that position and update their distance by 1 and mark it visited. For eg :
S..
 ..F
when starting from S we push into the queue positions (0,1), (0,2), (1,0), (1,1), consider 0 based indexing, update their position and mark them visited.
But while pushing into the queue just checking whether that position has been visited wont do.
Because consider the case
S..
XX.
..F
here, from (0,1) you can visit (1,2) and update its distance and mark it visited, and when you check for (0,2) you will see (1,2) is visited and not check further. This is incorrect because for optimal solution you must visit (1,2) and (2,2) from here. Hence even if the square is visited you should visit it again if it can be reached from the current position in 1 move.
Look code for further details.

RECOMMENDED QUESTION :

Try your hands on this question : Headshot

SOLUTION :

#include <iostream> #include <stdio.h> #include <queue> using namespace std; struct point { int x,y; }; int X[] = {-1, -1, -1, 0, 0, 1, 1, 1}; int Y[] = {-1, 0, 1, -1, 1, -1, 0, 1}; int n,m; char str[1005][1005]; int dist[1000][1000]; bool check(point t) { if(t.x >=0 && t.x <n && t.y >=0 && t.y <m && str[t.x][t.y] != 'X') return true; return false; } int main() { int t; scanf("%d", &t); while(t--) { scanf("%d %d", &n, &m); for(int i=0; i<n; i++) scanf("%s", str[i]); queue<point> q; point start, final; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { dist[i][j] = 0; if(str[i][j] == 'S') { start.x = i; start.y = j; dist[i][j] = 1; } else if(str[i][j] == 'F') { final.x = i; final.y = j; } } } q.push(start); while(!q.empty()) { point temp = q.front(); q.pop(); for(int i=0; i<8; i++) { point copy = temp; copy.x += X[i]; copy.y += Y[i]; while(check(copy)) { if(dist[copy.x][copy.y] == 0) { dist[copy.x][copy.y] = dist[temp.x][temp.y] + 1; q.push(copy); } else if(dist[copy.x][copy.y] != dist[temp.x][temp.y]+1) break; copy.x += X[i]; copy.y += Y[i]; } } } cout << dist[final.x][final.y]-1 << endl; } return 0; }

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;

}