# Maze with N doors and 1 Key

Moderate
0/80
Average time to solve is 15m
Contributed by

## 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, Images )
Constraints:
1 <= 'T' <= 100
1 <= 'N' <= 100
'MAZE[i][j]' = {0, 1}

Time Limit: 1 sec
1
3
0 0 0
1 0 1
0 1 0
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).

1
2
1 0
0 1
NO
Console