Question #44943

Given a square maze (A) of dimension N, every entry (Aij) in the maze is either an open cell 'O' or a wall 'X'. A rat can travel to its adjacent locations (left, right, top and bottom), but to reach a cell, it must be open. Given the locations of R rats, can you find out whether all the rats can reach others or not?
Input Format:
Input will consist of three parts, viz.
1. Size of the maze (N)
2. The maze itself (A = N * N)
3. Number of rats (R)
4. Location of R rats (Xi, Yi)
Note:
(Xi,Yi) will represents the location of the i-th rat.
Locations are 1-index based.
Output Format:
Print "Yes" if the rats can reach each other, else print "No"
Constraints:
1<=N<=350
Aij = {'O','X'}
1<=R<=N*N
1<=Xi<=N
1<=Yi<=N

Expert's answer

`//Answer on Question#44943 - Progamming - C++`

#include <iostream>

#include <string>

using namespace std;

const int MAX_N = 350;

// depth-first-search algorithm

// takes the maze, the size of the maze. the current position in the maze

int dfs(string maze[], int N, int x, int y) {

int rats = 0;

if (x < 0 || x >= N) return rats; // the position is not in the maze

if (y < 0 || y >= N) return rats; // the position is not in the maze

if (maze[x][y] != 'O' && maze[x][y] != 'R') return rats; // the position isn't open

if (maze[x][y] == 'R') ++rats;

maze[x][y] = 'X'; // make the cell closed beacuse we already visited it

static const int dx[4] = {-1, 0, 1, 0};

static const int dy[4] = {0, 1, 0, -1};

// visit all adjacent cells

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

int nx = x + dx[i];

int ny = y + dy[i];

rats += dfs(maze, N, nx, ny);

}

return rats;

}

int main() {

int N;

cin >> N;

string maze[MAX_N];

for (int i = 0; i < N; ++i) {

cin >> maze[i];

}

int R;

cin >> R;

for (int i = 0; i < R; ++i) {

int X, Y;

cin >> X >> Y;

--X; --Y;

maze[X][Y] = 'R';

}

// run the depth-first-search algorithm for unvisited cell

for (int i = 0; i < N; ++i) {

for (int j = 0; j < N; ++j) {

int rats = dfs(maze, N, i, j);

if (rats == R) { // all rats are in the same connected component

cout << "Yes" << endl;

return 0;

} else if (rats > 0) { // there is a rat in a component with not all other rats

cout << "No" << endl;

return 0;

}

}

}

}

## Comments

Assignment Expert03.08.15, 17:35Dear rethna, You're welcome. We are glad to be helpful.

If you liked our service please press like-button beside answer field. Thank you!

rethna03.08.15, 12:06than you sir

## Leave a comment