New update is available. Click here to update.

Maze with N doors and 1 Key

MEDIUM

15 mins

8 upvotes

Dynamic Programming

Matrices (2D Arrays)

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

Maze with N doors and 1 Key

Contributed by

Ambuj verma

Medium

0/80

Avg time to solve 15 mins

Success Rate 85 %

8 upvotes

Problem Statement

You are given an 'N * N' 'MAZE' where some cells have a door while some do not and a key that can be used only once to open a door.

You need to find if there exists a path from the top-left cell to the bottom right cell of the maze provided only downward and rightward movements are allowed.

Note:

1. You have only one key. And a key once used is exhausted and no more available with you during the journey through that path in a maze.

2. A cell with value 1, means the door or path is closed. And you have to spend a key to open the door/ reach that cell.

3. A cell with value 0, means that the cell is free to move / door is always open.

4. Top left cell in the maze and bottom-right cell in the maze may also have a door.

5. Downwards movement: From cell (i, j) to (i, j+1).

6. Rightwards movement: From cell (i, j) to (i+1, j).

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

Input Format:

The first line of the input contains an integer 'T' denoting the number of test cases. 
Then 'T' test cases follow.

The first line of each test case contains the side length 'N' of the square binary maze.

Then 'N' lines follow.
Each line contains 'N' space-separated integers 1 or 0 denoting whether the cell has a door or not.

Output Format:

For each test case, print in a separate line “YES” if the bottom right corner is reachable, else print “NO”.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= 'T' <= 100
1 <= 'N' <= 100
'MAZE[i][j]' = {0, 1}

Time Limit: 1 sec

Sample Input 1:

Sample Output 1:

YES

Explanation for Sample Input 1:

There are 3 paths possible; two paths have been shown in the below diagram. Note that we are using our only key at the cell (2,3) (1-based indexing).

Sample Input 2:

Sample Output 2:

NO

Auto

Console