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

Question

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

Answer 1

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