New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Rat In a Maze All Paths

Contributed by

Deep Mavani

Medium

0/80

Avg time to solve 40 mins

Success Rate 60 %

203 upvotes

Problem Statement

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.

Detailed explanation ( Input/output format, Notes, Constraints, Images )

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

Sample Input 1 :

Sample Output 1 :

1 0 0 1 0 0 1 1 1

Explanation for Sample Output 1:

Only 1 path is possible which contains coordinate < (1,1), (2,1), (3,1), (3,2) and (3,3) >

So our path matrix will look like this:

1 0 0
1 0 0
1 1 1

Which is returned from left to right and then top to bottom in one line.

Sample Input 2 :

2
1 0
0 1

Sample Output 2 :

 [Blank]

Explanation for Sample Output 2:

As no path is possible to the last cell, a blank vector will be returned and nothing is printed.

Auto

Console