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
Example 1
Input:
3
O O X
O X O
O O X
4
1 1
1 2
2 1
3 2
Output:
Yes
Example 2
Input:
3
O O X
O X O
O O X
4
1 1
1 2
2 1
2 3
Output:
No
Solution: In 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;
}
}
}
}Solution: In Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bufferedReader.readLine());
char[][] A = new char[N][N];
for (int i = 0; i < N; i++) {
A[i] = bufferedReader.readLine().toCharArray();
}
int R = Integer.parseInt(bufferedReader.readLine());
int[] X = new int[R],
Y = new int[R];
for (int i = 0; i < R; i++) {
String[] inputs = bufferedReader.readLine().split(" ");
X[i] = Integer.parseInt(inputs[0]) - 1;
Y[i] = Integer.parseInt(inputs[1]) - 1;
}
boolean[][] visited;
for (int i = 1; i < R; i++) {
visited = new boolean[N][N];
if (!visit(A, X[i], Y[i], X[0], Y[0], visited)) {
System.out.println("No");
return;
}
}
System.out.println("Yes");
}
private static boolean visit(char[][] A, int X1, int Y1, int X2, int Y2, boolean[][] visited) {
if (X1 == X2 && Y1 == Y2) {
return true;
}
if (A[X1][Y1] == 'X' || visited[X1][Y1]) {
return false;
}
visited[X1][Y1] = true;
if (X1 - 1 >= 0 && visit(A, X1 - 1, Y1, X2, Y2, visited)) {
return true;
}
if (X1 + 1 < A.length && visit(A, X1 + 1, Y1, X2, Y2, visited)) {
return true;
}
if (Y1 - 1 >= 0 && visit(A, X1, Y1 - 1, X2, Y2, visited)) {
return true;
}
if (Y1 + 1 < A.length && visit(A, X1, Y1 + 1, X2, Y2, visited)) {
return true;
}
return false;
}
}Also Checkout