99 006
Assignments Done
99%
Successfully Done
In May 2021

# Answer to Question #44945 in C for sibiaravind

Question #44945
Problem : Trace the Rats

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

Sample Input and Output
SNo. Input Output
1
3
O O X
O X O
O O X
4
1 1
1 2
2 1
3 2

Yes

2
3
O O X
O X O
O O X
4
1 1
1 2
2 1
2 3

No
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!