# Robot Grid

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

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 the current cell is blocked i.e
- 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 the current cell is blocked i.e
- If
**FIND_PATH_HELPER(0, 0)**returns true**,**then return the list**PATH,**otherwise return a list having a single element [-1, -1].