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...
Amazon Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
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

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter