# Robot Grid

Posted: 8 Mar, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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
``````