Last Updated: 5 Mar, 2021

Rat In A Maze

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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:

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.
Create another matrix/grid called ‘VISITED’ to keep track of all visited and unvisited cells
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.:-
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.
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.
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.

Solve now