Robot Grid

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
3 upvotes
Asked in companies
AmazonMicrosoftVMware Inc

Problem statement

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]]
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2 2
0 1
1 1
3 4
0 0 0 0
1 1 0 0 
0 1 1 0
Sample Output 1:
-1 -1
 0 0
 0 1
 0 2
 0 3
 1 3
 2 3
Explanation of Sample Input 1:
Test case 1:
All cells except (0, 0) are blocked, so it is not possible for the robot to reach the cell (1, 1).    

Test case 2:
See the problem statement for an explanation.
Sample Input 2:
2
1 1
0
2 3
0 0 1
1 0 1
1 1 0
Sample Output 2:
0 0
-1 -1
Hint

Incrementally find the next possible move of the robot that can lead to a valid path, if no such move exists then backtrack to previous moves.

Approaches (2)
Backtracking

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].
Time Complexity

O(2^(N+M)), where ‘N’, ‘M’  is the number of rows and columns in the given grid.

 

In each recursive step, we have two choices either to move ‘Right’ or ‘Down’, also there will be (N+M-2) recursive step as the length of the path in the grid to reach cell (N-1, M-1) from (0, 0) will be manhattan distance between them, which will be N+M -2. So overall we will have 2^(N+M-2) recursive calls in the worst case, each of these calls takes O(1) time. Thus, the overall complexity will be O(2^(N+M)).

Space Complexity

O(N+M),  where ‘N’, ‘M’  is the number of rows and columns in the given grid.

 

The recursion depth is of the order of N+M as the length of the path is N+M-2,  and space used by the list path is also of the order of  N+M. Thus overall space complexity will be O(N+M + N + M) = O(N + M).

Code Solution
(100% EXP penalty)
Robot Grid
Full screen
Console