Paths in a Maze

Easy
0/40
22 upvotes
Asked in companies
Expedia GroupAmazonMeesho

Problem statement

You are given a 2-D matrix consisting of 0’s and 1’s with ‘N’ rows and ‘N’ columns, you are supposed to find all paths from the cell (0,0) (top-left cell) to the cell (N-1, N-1)(bottom-right cell). All cells with value 0 are blocked and cannot be travelled through while all cells with value 1 are open.

If you are currently at cell (x,y) then you can move to (x+1,y)(denoted by ‘D’), (x-1,y)(denoted by ‘U’), (x,y+1)(denoted by ‘R’), (x,y-1)(denoted by ‘L’) in one move. You cannot move out of the grid.

Example :

Example

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases follow.

The first line of each test case contains a single integer ‘N’ denoting the number of rows and columns in the given matrix.

Next ‘N’ lines contain ‘N’ single space-separated integers each denoting the elements in the matrix.
Output Format : 
For each test case, print all paths from (0,0) to (N-1, N-1) separated by a single space.

The output of every test case will be printed in a separate line.
Note : 
You don’t need to print anything; It has already been taken care of.
Constraints : 
1 <= T <= 5
1 <= N <= 5
0 <= ARR[i][j] <= 1

Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of rows and columns of the given matrix, and ARR[i] denotes the value of the cell (i,j) in the given matrix.

Time Limit: 1 sec
Sample Input 1 :
2
2
1 1
1 1
2
1 0
1 1
Sample Output 1 :
DR RD
DR
Explanation of Sample Input 1 :
In the first test case, there are two paths from (0,0) to (1,1). The first path is (0,0)->(1,0)->(1,1) and the second path is (0,0)->(0,1)->(1,1)

In the second test case, there is only one path since the cell at (0,1) is blocked. The path is (0,0)->(1,0)->(1,1).
Sample Input 2 :
2
3
1 0 1
1 0 0
1 1 1
3
1 1 1
1 0 1
1 1 1
Sample Output 2 :
DDRR
DDRR RRDD
Explanation of Sample Input 2 :
In the first test case, there is only one path from (0,0) to (2,2). The path is (0,0)->(1,0)->(2,0)->(2,1)->(2,2).

In the second test case, there are two paths from (0,0) to (2,2). The first path is (0,0)->(1,0)->(2,0)->(2,1)->(2,2). and the second path is (0,0)->(0,1)->(0,2)->(1,2)->(2,2).
Hint

Can you think about exploring all possible paths using recursion?

Approaches (1)
Recursion Based Approach

The idea is to use recursion to try all possible paths and include the paths in our answer through which we can reach the cell (N-1, N-1).

 

The steps are as follows:
 

  1. Let’s define a recursive function as allPossiblePaths( i, j,  currentPath, allPaths, visited, arr). Here, ‘i’ and ‘j’ denote the current cell, i.e. (i,j), “currentPath” is a string which denotes our current path from (0,0) to (i,j), and “allPaths” is an array for storing all paths from (0,0) to (N-1, N-1), “visited” is a matrix of size N*N which we will use to mark the cells we have already visited and “arr” is the given matrix.
  2. Start from the cell (0,0) and recursively explore all paths; let’s say our current cell is (i,j).
    1. If the value of the current cell is 0, then return because this cell is blocked.
    2. Otherwise, if the current cell is (N-1, N-1) then return after adding the “currentPath” to “allPaths” because our current path is a valid path from (0,0) to (N-1, N-1).
    3. Mark visited[i][j] as true.
    4. If (i+1, j) is a valid cell in the matrix and visited[i+1][j] is false then, add ‘D’ (denoting down) to the “currentPath” and recursively call allPossiblePaths( i+1, j, currentPath, allPaths, visited, arr) to traverse all possible paths from (i+1, j) . After this pop the ‘D’ from “currentPath” because we have explored paths from (i+1, j).
    5. If (i-1, j) is a valid cell in the matrix and visited[i-1][j] is false then, add ‘U’ (denoting up) to the “currentPath” and call allPossiblePaths(i-1, j, currentPath, allPaths, visited, arr) to traverse all possible paths from (i-1, j) . After this pop the ‘U’ from “currentPath” because we have explored paths from (i-1, j).
    6. If (i, j+1) is a valid cell in the matrix and visited[i][j+1] is false then, add ‘R’ (denoting right) to the “currentPath” and call allPossiblePaths(i, j+1, currentPath, allPaths, visited, arr) to traverse all possible paths from (i, j+1) . After this pop the ‘R’ from “currentPath” because we have explored paths from (i, j+1).
    7. If (i, j-1) is a valid cell in the matrix and visited[i][j-1] is false then, add ‘L’(denoting left)  to the “currentPath” and call allPossiblePaths(i, j-1, currentPath, allPaths, visited, arr) to traverse all possible paths from (i,j-1) . After this pop the ‘L’ from “currentPath” because we have explored paths from (i, j-1).
    8. Now we have traversed all paths from (i,j) so we will mark visited[i][j] as false.
  3. Return “allPaths” array as this will contain all possible paths from (0,0) to (N-1, N-1).
Time Complexity

O(3 ^ (N ^ 2)), where ‘N’ is the number of rows in the given matrix.

 

As there are at most 3 unvisited neighbouring cells for any cell, we will make a maximum of 3 recursive calls from any cell, and there are a total of N ^ 2 cells. Thus, the total Time Complexity will be  O(3 ^ (N ^ 2)).

Space Complexity

O(3 ^ (N ^ 2)), where ‘N’ is the number of rows in the given matrix.

 

When there are no blocked cells in the matrix, our answer will contain 3 ^ (N ^ 2) cells. Thus the total Space Complexity is O(3 ^ (N ^ 2) ).

Code Solution
(100% EXP penalty)
Paths in a Maze
Full screen
Console