All submissions for this problem are available.
One thing Tom wants more than to eat Jerry is to not let Jerry have his favorite cheese cube.
Tom, Jerry and the cheese-cube are present in an m x n grid.
Now Tom and Jerry both set some traps for each other. There are some cells with traps set by Jerry for Tom and some with traps set by Tom for jerry. We also know the position of cheese-cube and initial positions of Tom and Jerry.
Given that both Tom and Jerry can move to any adjacent cell (horizontal, vertical or diagonal), which is not a trap for them taking unit time for each move, you have to print if there is a way for jerry to reach the cheese-cube before Tom reaches.
If one of them cannot reach the cheese-cube, assume his time to be infinite. However, if both of them cannot reach the cheese-cube, print “Cheese”.
First line contains an integer T, number of test cases.
For each test case
- First line contains two space separated integers m and n, dimensions of the grid.
- Next m lines contain n space separated integers each.
Each integer of grid has one of the following value- 0 - Cell is empty 1 - Cell has a trap for Tom 2 - Cell has a trap for Jerry 3 - Cell is initial position of Tom 4 - Cell is initial position of Jerry 5 - Cell has the cheese-cube
Print “Yes” if Jerry can reach the cheese-cube strictly before Tom, else “No”. (Quotes are for clarity). In case it is impossible for both of them to reach the cheese-cube print “Cheese”.
- 1 ≤ T ≤ 10
- 1 ≤ m,n ≤ 100
- 5 ≤ m*n
- 0 ≤ Value of each cell ≤ 5
Input: 1 4 4 3 0 0 0 1 0 2 4 5 0 1 0 0 1 2 0 Output: No
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6|
Fetching successful submissions
If you are still having problems, see a sample solution here.