Rat In A Maze

Easy
0/40
Average time to solve is 15m
profile
Contributed by
184 upvotes
Asked in companies
OlaIBMGoldman Sachs

Problem statement

You are given a starting position for a rat which is stuck in a maze at an initial point (0, 0) (the maze can be thought of as a 2-dimensional plane). The maze would be given in the form of a square matrix of order 'N' * 'N' where the cells with value 0 represent the maze’s blocked locations while value 1 is the open/available path that the rat can take to reach its destination. The rat's destination is at ('N' - 1, 'N' - 1). Your task is to find all the possible paths that the rat can take to reach from source to destination in the maze. The possible directions that it can take to move in the maze are 'U'(up) i.e. (x, y - 1) , 'D'(down) i.e. (x, y + 1) , 'L' (left) i.e. (x - 1, y), 'R' (right) i.e. (x + 1, y).

Note: 
Here, sorted paths mean that the expected output should be in alphabetical order.
For Example: 
Given a square matrix of size 4*4 (i.e. here 'N' = 4):
1 0 0 0
1 1 0 0
1 1 0 0
0 1 1 1 
Expected Output:
DDRDRR DRDDRR 
i.e. Path-1: DDRDRR and Path-2: DRDDRR

The rat can reach the destination at (3, 3) from (0, 0) by two paths, i.e. DRDDRR and DDRDRR when printed in sorted order, we get DDRDRR DRDDRR.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains an integer 'N', which denotes the dimensions of the square matrix (maze).

Then 'N' lines follow. Each line contains 'N' space-separated integers denoting the values which would either be 0 denoting a blocked path or 1 denoting the available path in the maze, respectively.
Output format: 
For the given maze, print the vector/list of strings representing all the possible paths that the rat can take to reach from source to destination in the maze in sorted order.

Output for each test case will be printed in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
2 <= N <= 5
0 <= MATRIX[i][j] <= 1

Where N is the size of the square matrix.

Time Limit: 1sec
Sample Input 1:
4
1 0 0 0 
1 1 0 1
1 1 0 0
0 1 1 1
Sample Output 1:
DDRDRR DRDDRR
Explanation For Sample Input 1:
The rat can reach the destination at (3, 3) from (0, 0) by two paths, i.e. DRDDRR and DDRDRR when printed in sorted order, we get DDRDRR DRDDRR.
Sample Input 2:
2
1 0
1 0
Sample Output 2:
[]
Explanation For Sample Input 2:
As no valid path exists in Sample input 2 so we return an empty list.
Hint

Can you traverse the maze in a depth-first search fashion?

Approaches (1)
Bactracking

Approach: We can start the traversal of the paths from the rat’s starting position, i.e. (0,0) keeping track of the visited cells during the traversal. We will recursively go through all the paths possible until the last index of the grid (destination) is reached, and add the path information using which the rat successfully reached the end.

 

Algorithm is as follows:

 

  1. Take the starting position of the rat as (0, 0) and start traversing the valid cells (which are unblocked, i.e. with value 1) through adjacent cells in the following order Down -> Left -> Right -> Up so that we can automatically get sorted paths in alphabetical order.
  2. Create another matrix/grid called ‘VISITED’ to keep track of all visited and unvisited cells
  3. Recursively look for the valid set of paths possible from the starting cell until we reach the destination or an invalid cell. We keep setting the respective ‘VISITED’ matrix/grid value of the cell to true. I.e.:- 
  4. If the move is possible, then move to that cell while storing the character corresponding to the move, i.e. either (D, L, R, U) and recursively start looking for a valid move until the destination (i.e. (n - 1, n - 1)) is reached by the rat.
  5. Keep marking the cells as visited. When all the paths possible are traversed from that cell, unmark that cell for other different paths and remove the character from the path formed.
  6. As soon as the last index of the grid(bottom right), our destination is reached, we store the traversed path information in a vector/list.
Time Complexity

O(3^(N^2)), where N is the dimension of the square matrix.

 

Now, since there are N^2 cells in total and from each cell, there can only be three unvisited neighbouring cells. So the time complexity O(3^(N^2)).

Space Complexity

O(N^2), where N is the dimension of the square matrix.

 

As there can be at most N^2 cells in the answer for each possible path available for each cell with N^2 cells in total, so the space complexity is also O(N^2).

Code Solution
(100% EXP penalty)
Rat In A Maze
Full screen
Console