Last Updated: 8 Mar, 2021
Robot Grid
Moderate
Asked in companies
Consider a grid consisting of ‘N’ rows and ‘M’ columns. Rows are numbered from 0 to ‘N’-1 and columns are numbered from 0 to ‘M’-1. The cell at the intersection of the ith row and the jth column is represented as (i, j).
Initially a robot is standing at (0, 0). The robot can only move in two directions, ‘Right’ and ‘Down’. I.e if the robot is at (r, c), then it can move to (r, c+1) or (r+1, c). Some cells in the grid are blocked i.e robot cannot step on them.
You are given a matrix ‘GRID[][]’ of size N*M, where GRID[i][j] = 1 if cell (i, j) is blocked otherwise cell (i, j) = 0. Your task is to find the lexicographically smallest path for the robot from (0, 0) to (N-1, M-1). A path is represented as a list of cells in the same order in which the robot should visit. See the example for more clarity.
Note
1. In lexicographical order cell (r1, c1) comes before cell (r2, c2) if either r1 < r2 or (r1 = r2 and c1 < c2).
2. If there is no possible path, then return a list with a single element [-1, -1].
3. It is guaranteed that cell (0, 0) is not blocked.
Example:
Consider the following 3*4 grid -:
[
[0 0 0 0]
[1 1 0 0]
[0 1 1 0]
]
There are two possible paths to reach cell (2, 3) from (0, 0).
Path-1 -> [[0, 0], [0, 1], [0, 2], [0, 3], [1, 3], [2, 3]]
Path-2 -> [[0, 0], [0, 1], [0, 2], [1, 2], [1, 3], [2, 3]]
Clearly, Path-1 is lexicographically smaller than Path-2.
Thus we should return list [[0, 0], [0, 1], [0, 2], [0, 3], [1, 3], [2, 3]]
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases. then ‘T’ test cases follow.
The first line contains two space-separated integers ‘N’, ‘M’ representing the number of rows and columns respectively.
Then next ‘N’ lines follow in each case, Each of these ‘N’ lines consists of ‘M’ space-separated integers. These ‘N’ lines represent the ‘grid’.
Output format :
For each test case, if there exists a path, then return a 2d array of N+M-1 rows which has two integers, representing the row and column of cells in the lexicographically smallest path.
Otherwise, return a 2d array consisting of -1 -1.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 10^2
1 <= M <= 10^2
0 <= GRID[i][j] <= 1
Time limit: 1 sec
Approaches
In this approach, we incrementally build the solution PATH. In each step, we check if it is possible to reach the target cell i.e (N-1, M-1) by moving the robot to ‘Right’. If it is impossible to reach the target cell by moving ‘Right’ then we remove that move and try moving the robot ‘Down’. If both of them do not work out then we go to the previous stage and remove the moves in the previous stages. If we reach the initial stage back then we say that no solution exists.
Note that we will try moving ‘Right’ first and then Down, this will ensure that we try the path in lexicographic order.
Algorithm
- Create an empty list ‘PATH’.
- Create a recursive function FIND_PATH_HELPER(r, c), where ‘r’ and ‘c’ are the current row and column in which the robot stands. This function will return true if it is possible to reach (N-1, M-1) from (r, c) otherwise it will return false. In each recursive step of this function, we will do the following -:
- If the current cell is blocked i.e GRID[r][c] = 1, then return false.
- Push the current cell in the list PATH.
- If the current cell is the target cell if r = N-1 and c = M-1, then return true.
- Recursively call FIND_PATH_HELPER(r, c+1) (if c+1 < M) and FIND_PATH_HELPER(r+1, c) (if r+1 < N), if any one of them return true, then return true, otherwise, pop the current cell from the list PATH and return false.
- If FIND_PATH_HELPER(0, 0) returns true, then return the list PATH, otherwise return a list having a single element [-1, -1].
We can optimize the previous approach by using a ‘DP[][]’ table of dimension N*M to avoid repeated work by memoizing the result of subproblems. If it is possible to reach (N-1, M-1) from (i, j) then DP[i][j] will be 1, otherwise, it will be 0.
Algorithm
- Create an empty list ‘PATH’.
- Create an integer matrix ‘DP[][]’ of dimension N*M, and fill it with -1.
- Create a recursive function FIND_PATH_HELPER(r, c), where ‘r’ and ‘c’ are the current row and column in which the robot stands. This function will return true if it is possible to reach (N-1, M-1) from (r, c) otherwise it will return false. In each recursive step of this function, we will do the following -:
- If the current cell is blocked i.e GRID[r][c] = 1, then do DP[r][c]:= 0 and return false.
- If DP[r][c] = 0 then return false.
- Push current cell i.e (r, c) in the list PATH
- If DP[r][c] = 1, then return true.
- If the current cell is the target cell if r = N-1 and c = M-1, then return true.
- Recursively call FIND_PATH_HELPER(r, c+1) (if c+1 < M) and FIND_PATH_HELPER(r+1, c) (if r+1 < N), if any one of them return true, then do DP[r][c]:= 1 and return true, otherwise, pop the current cell from the list PATH , do DP[r][c]:= 0 and return false.
- If FIND_PATH_HELPER(0, 0) returns true, then return the list PATH, otherwise return a list having a single element [-1, -1].
Similar problems