##
__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.

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

What do the X and Y integer arrays do?

ReplyDeleteGot it, they are the indices of the neighboring nodes in order.

Deletethey help you to move in the 8 directions

ReplyDeleteWhy are we manipulating the value of copy again after the break statement?

ReplyDeleteThis is a life saver. Really pretty code, thanks.

ReplyDelete:)

Delete