Bob's Game

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in company
BNY Mellon

Problem statement

Bob is playing a game where there is a grid of size ‘N’ X ‘M’, where each cell is either 0, 1, or 2.

0 means the cell is empty, 1 means the cell contains a block, and 2 means there is a guard present in that block. A guard can see in all four directions, i.e., left, right, up, down till there is a block or to the end of the grid if there are no blocks present in that direction.

For Example: 
0 0
0 0
2 1
In the above grid, if Bob is present at (0,1), he can't move to (0,0) because the cell at (0,0) is seen by the guard present at (2,0).

0 0
1 0
2 1
In the above grid, Bob can move from (0,1) to (0,0) since this cell is not seen by the guard at (2,0) due to the block present at (1,0).

At each step, one can move to any valid adjacent cells that share a common side with the current cell. A cell is valid if it is present inside the grid, empty, and not seen by any of the guards.

Now Bob can enter the grid from any of the four corners of the grid(if it is a valid cell) i.e, (0,0), (N - 1,0), (0,M - 1), (N - 1,M - 1), and he wants to reach a destination cell.

Can you tell whether Bob can reach the destination cell or not?

Note: 
If all the corner cells are invalid, then return false.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain a single integer ‘T’ denoting the number of test cases. Then ‘T’ test cases follow.

The first line of each test case will contain two space-separated integers ‘N’ and ‘M’, denoting the number of rows and number of columns, respectively.

The next ‘N’ lines of each test case will contain ‘M’ space-separated integers denoting the cell values of that corresponding row.

The next line of each test case will contain two space-separated integers denoting the row and column numbers of the destination cell. 

It is guaranteed that the integer values in the grid are either 0, 1, or 2.
Output Format : 
For each test case, print “YES” if Bob can reach the destination cell, else print “NO”.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 100
1 <= N,M <= 10^3
X[i][j] = { 0, 1, 2 }     0 <= i < N, 0 <= j < M

Where X[i][j] denotes the cell value of ith row and jth cell.

It is guaranteed that the sum of N*M over all test cases doesn’t exceed 10^6.

Time Limit: 1 sec.
Sample Input 1:
2
3 3
0 0 0
1 0 0
0 0 2
1 1
4 3
0 1 0
2 1 0
0 0 0
0 0 1
3 1
Sample Output 1:
YES
YES
Explanation For Sample Output 1:
For the first test case, Bob can reach the destination cell by the following path:
(0,0) -> (0,1) -> (1,1).

For the second test case, Bob can reach the destination cell by the following path:
(0,2) -> (1,2) -> (2,2) -> (2,1) -> (3,1).
Sample Input 2:
2
4 3
0 1 0
2 0 0
0 0 0
0 0 1
3 1
4 4
0 0 0 0
0 0 1 1
1 1 2 0
0 1 0 2
1 1
Sample Output 2:
NO
YES
Hint

Try to identify all the invalid cells and then use graph algorithms to traverse the grid.

Approaches (1)
Multi-source BFS on Grid(Optimized)

The approach is similar to the previous one, but here, we will not traverse all four directions for each guard. We will traverse the whole grid four times, and each time we will mark the seen cells by any guard in a particular direction. For example, in the first traversal, we can mark all the cells to the right of all the guards as invalid. In the next traversal, we can mark the left ones—similarly, upper and lower ones in the next two traversals.
 

After that, we will use multi-source bfs to traverse the grid and return true if the destination cell is visited, otherwise false.
 

Algorithm:
 

  • isValid function:
    • Checks whether a cell is valid or not.
       
  • leftright function:
    • Takes the grid and a direction as arguments and mark all the invalid cells in that particular direction(left or right).
    • Start iterating over the rows.
      • Declare a boolean variable flag as mark it as false.
      • Now choose the direction depending on the “dir” variable given as an argument.
      • Start iterating over the columns.
        • If the current cell has a guard, mark the flag as true.
        • Else if the current grid has a box, mark the flag as false.
        • Else if the flag is true, mark the current cell as invalid.
        • Change column as per the direction.
           
  • updown function:
    • Takes the grid and a direction as arguments and mark all the invalid cells in that particular direction(up or down).
    • Start iterating over the rows.
      • Declare a boolean variable flag as mark it as false.
      • Now choose the direction depending on the “dir” variable given as an argument.
      • Start iterating over the columns.
        • If the current cell has a guard, mark the flag as true.
        • Else if the current grid has a box, mark the flag as false.
        • Else if the flag is true, mark the current cell as invalid.
        • Change column as per the direction.
           
  • given function:
    • Mark all the invalid cells using the “leftright” and “updown” functions.
    • Declare a queue of pairs and push all the valid corners to it, and mark all of them as visited.
    • While the queue is not empty, take the front cell from the queue.
      • If it is the destination cell, return true.
      • Push all the valid adjacent cells to the queue which are not visited and mark them visited.
    • Finally, return false.
Time Complexity

O(n * m), where ‘n’ and ‘m’ are the number of rows and columns, respectively.

 

Since in every iteration, we are visiting every cell only once, the overall time complexity will be O(n * m). 

Space Complexity

O(n * m), where ‘n’ and ‘m’ are the number of rows and columns, respectively.

 

Since we are using a visiting grid of size n*m and a queue of order n*m, the overall time complexity will be O(n * m).

Code Solution
(100% EXP penalty)
Bob's Game
Full screen
Console