Maze with N Doors and 1 Key Problem Statement
You are given an N x N maze where some cells have doors, and you have a key that can be used only once to open a door. Determine if there exists a path from the top-left cell to the bottom-right cell of the maze, allowing only downward and rightward movements.
Input:
The first line of the input contains an integer 'T' denoting the number of test cases.
Then 'T' test cases follow.
Each test case begins with an integer 'N', the side length of the square binary maze.
Following are 'N' lines for each test case, with each line containing 'N' space-separated integers (either 1 or 0) that indicate whether each cell has a door or not.
Output:
For each test case, print "YES" if the bottom-right corner is reachable using the key, otherwise print "NO".
Example:
Input:
2
3
0 1 0
1 1 0
0 0 0
2
0 1
1 0
Output:
YES
YES
Constraints:
- 1 <= T <= 100
- 1 <= N <= 100
- MAZE[i][j] = {0, 1}
Note:
- You have only one key, and it is exhausted after one use.
- A cell with a value of 1 indicates a door, which you must open using the key to pass.
- A cell with a value of 0 indicates a free path and can be traversed without using the key.
- The top-left and bottom-right cells may also have doors.
- Only downward (from cell (i, j) to (i, j+1)) and rightward (from cell (i, j) to (i+1, j)) movements are allowed.
AnswerBot
3d
Determine if there exists a path from the top-left cell to the bottom-right cell of a maze with N doors and 1 key.
Use depth-first search (DFS) or breadth-first search (BFS) to explore possible paths t...read more
Help your peers!
Add answer anonymously...
Top Amazon Software Developer interview questions & answers
Popular interview questions of Software Developer
Top HR questions asked in Amazon Software Developer
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app