# Answer to Question #44943 in C++ for Rahul Jobanputra

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 &quot;Yes&quot; if the rats can reach each other, else print &quot;No&quot; Constraints: 1&lt;=N&lt;=350 Aij = {'O','X'} 1&lt;=R&lt;=N*N 1&lt;=Xi&lt;=N 1&lt;=Yi&lt;=N
``//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 mazeint 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 = {-1, 0, 1, 0};   static const int dy = {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;         }       }   }}``

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Assignment Expert
03.08.15, 17:35

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

rethna
03.08.15, 12:06

than you sir