Rat In a Maze All Paths
You are given a 'N' * 'N' maze with a rat placed at 'MAZE[0][0]'. Find and print all paths that rat can follow to reach its destination i.e. 'MAZE['N' - 1]['N' - 1]'. Rat can move in any direction ( left, right, up and down).

Value of every cell in the 'MAZE' can either be 0 or 1. Cells with value 0 are blocked means the rat cannot enter into those cells and those with value 1 are open.

Input Format:

The first line of input contains an integer 'N' representing the dimension of the maze. The next 'N' lines of input contain 'N' space-separated integers representing the type of the cell.

Output Format :

For each test case, return the path from the start position to the destination position and only cells that are part of the solution path should be 1, rest all cells should be 0. Output for every 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:

1

Question

Rat In a Maze All Paths

You are given a 'N' * 'N' maze with a rat placed at 'MAZE[0][0]'. Find and print all paths that rat can follow to reach its destination i.e. 'MAZE['N' - 1]['N' - 1]'. Rat can move in any direction ( left, right, up and down).

Value of every cell in the 'MAZE' can either be 0 or 1. Cells with value 0 are blocked means the rat cannot enter into those cells and those with value 1 are open.

Input Format:

The first line of input contains an integer 'N' representing the dimension of the maze.

The next 'N' lines of input contain 'N' space-separated integers representing the type of the cell.

Output Format :

For each test case, return the path from the start position to the destination position and only cells that are part of the solution path should be 1, rest all cells should be 0.

Output for every 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:

1 <= N <= 10
0 <= MAZE[i][j] <=1

Where 'MAZE[i][j]' denotes the value in the cell of 'MAZE'.

Time Limit: 1 sec

Accepted Answer

Practise many grid problems

Accepted Answer

Backtracking Approach

Initialize, all the cells of the solution matrix used to print the path matrix to 0. First, you cannot make use of the existing maze to print the solution maze as you have to distinguish b/w 1 of maze or 1 of ‘SOLUTION matrix.

Form a recursive function, which will follow a path and check if the path reaches the destination or not. If the path does not reach the destination then backtrack and try other paths. But in case it reaches the destination print the current ‘SOLUTION’ matrix.

The steps are as follows:

f('i', ‘j'):

If rat reaches the destination, print the solution matrix.
Else:
- If not valid('MAZE[i][j]' ) return
- Else ‘SOLUTION[i][j]' =1
- f(i-1,j) ; f(i+1,j) , f(i, j-1) , f(i,j+1) // Recursive calls
- ‘SOLUTION[i][j]' = 0 // Backtracking

Space Complexity: O(1)Explanation:

O(N * N), Where ‘N’ is the dimension of the matrix.

Since the extra space used to create 'SOLUTION matrix of size N * N. Thus the space complexity will be O(N * N).

Time Complexity: OtherExplanation:

O(4 ^ (N ^ 2)), Where ‘N’ is the dimension of the matrix.

Since we can call 4 recursive calls from each cell in ‘N’ * ‘N’ board, Thus the time complexity will be O(4 ^ (N ^ 2)).

Accepted Answer

trivial, start with {0,0} nd simply change it to -1 look for all four direction [ifValid] via recursion, change it back to 1;

if you reach {n-1,n-1} just add this to a answer vector.

Return size of this vector

You are given a 'N' * 'N' maze with a rat placed at 'MAZE[0][0]'. Find and print all paths that rat can follow to reach its destination i.e. 'MAZE['N' - 1]['N' - 1]'. Rat can move in any direction ( left, right, up and down).

Value of every cell in the 'MAZE' can either be 0 or 1. Cells with value 0 are blocked means the rat cannot enter into those cells and those with value 1 are open.

Input Format:

Output Format :

Note:

Constraints:

Top Uber SDE-2 interview questions & answers

Popular interview questions of SDE-2

You are given a 'N' * 'N' maze with a rat placed at 'MAZE[0][0]'. Find and print all paths that rat can follow to reach its destination i.e. 'MAZE['N' - 1]['N' - 1]'. Rat can move in any direc­tion ( left, right, up and down).

Value of every cell in the 'MAZE' can either be 0 or 1. Cells with value 0 are blocked means the rat can­not enter into those cells and those with value 1 are open.

Input Format:

Output Format :

Note:

Constraints:

Top Uber SDE-2 interview questions & answers

Popular interview questions of SDE-2

You are given a 'N' * 'N' maze with a rat placed at 'MAZE[0][0]'. Find and print all paths that rat can follow to reach its destination i.e. 'MAZE['N' - 1]['N' - 1]'. Rat can move in any direction ( left, right, up and down).

Value of every cell in the 'MAZE' can either be 0 or 1. Cells with value 0 are blocked means the rat cannot enter into those cells and those with value 1 are open.