Wednesday 7 June 2017

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; }

12 comments:

  1. What do the X and Y integer arrays do?

    ReplyDelete
    Replies
    1. Got it, they are the indices of the neighboring nodes in order.

      Delete
  2. they help you to move in the 8 directions

    ReplyDelete
  3. Why are we manipulating the value of copy again after the break statement?

    ReplyDelete
  4. This is a life saver. Really pretty code, thanks.

    ReplyDelete
  5. else if(dist[copy.x][copy.y] != dist[temp.x][temp.y]+1)
    break;
    copy.x += X[i];
    copy.y += Y[i];
    }


    Why these lines are used???
    Please explain.

    ReplyDelete
    Replies
    1. We do a break beacause that path is already travelled.
      BTW the copy += x part is outside the else {} . So basically it means that if path is not travelled move in that direction else break.

      Delete
  6. I think this should be updated in this code:

    else if(dist[copy.x][copy.y] >= dist[temp.x][temp.y]+1)
    dist[copy.x][copy.y] = dist[temp.x][temp.y] + 1;
    else
    break;

    ReplyDelete
    Replies
    1. If you notice it can never be > because if it is already visited then either it will be less or equal to.

      Delete
    2. that means if dist[copy.x][copy.y]==dist[temp.x][temp.y] it is visited from some other direction and we continue moving on without pushing this cell and if it is not equal it is visited from same direction and we stop moving in the same direction since we have already done that...excellent solution
      How much time it took you to reach this solution?

      Delete
  7. Please explain the line:else if(dist[copy.x][copy.y] != dist[temp.x][temp.y]+1) break;
    Why did we do this??

    ReplyDelete