Last Updated: 17 Dec, 2020

Paths in a Maze

Easy

Asked in companies

Solve now

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

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

Solve now

Approaches

01 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:

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.
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.
Return “allPaths” array as this will contain all possible paths from (0,0) to (N-1, N-1).

Solve now