Wednesday, 7 June 2017

QUEEN

Standard

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

6 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