New update is available. Click here to update.

Robot Grid

Posted: 8 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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