Last Updated: 30 Oct, 2020
Maze with N doors and 1 Key
Moderate
Asked in company
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).
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
Approaches
- This problem can be solved using Recursion.
- If the current position in the maze (x, y) is set to 0, that means no key is required to open the current door. Check if it is destination return true. Else, move to next possible positions (right and bottom cells, if they lie in the maze).
- If the current cell in the maze has a door(i.e the value of the cell is 1), then the key is needed to open the door. If the key has not been used previously in this path, use the key, i.e. set key = false. Check if its destination, else move to next possible positions (right and bottom cells, if they lie in the maze).
- If any path reaches destination / bottom-right cell of the maze, print “YES”. Else print “NO”.
- At any cell (x, y), to know if the bottom-right cell is reachable from this cell. We need two information: whether the path from (x+1, y) to the bottom-right cell and the path from (x, y+1) to the bottom-right cell is reachable.
- Similarly, the path from (x+1, y-1) also depends on the path from (x+1, y) cell to the bottom-right cell.
- Thus we see both conditions of DP being satisfied: optimal substructure and overlapping subproblem.
The top-down DP solution to the problem is as follows:
- Create ‘DP’ table of size (N+1)*(N+1) and initialize it to 0, as we are assuming that each cell can be reached without the use of the key
- ‘DP[i][j]’ means minimum no of maximum keys required to reach this cell in the ‘MAZE’. A value of 2 means, it requires more than or equal to 2 keys to reach the cell.
- The base case is: if ‘MAZE[0][0]’ = 1, then ‘DP[0][0]’ = 1;
- Now iterate through the maze in a left-right top-down fashion:
- If the current row equals 0, then the path would come from the top cell. In such case ‘DP[i][j]’ = min(2, ‘MAZE[i][j]’ + ‘DP[i-1] [j]’).
- If the current column equals 0, then the path would come from the left cell. In such case, dp[i][j] = min(2, ‘MAZE[i][j]’ + ‘DP[i][j-1]’).
- For any cell not aligned with the top and left sides, it will have a minimum of keys required till the top and left cells respectively. For such cases, ‘DP[i][j]’ = min(2, ‘MAZE[i][j]’ + min('DP[i-1][j]', ‘DP[i][j-1]’)).
- If the ‘DP’ value at the last cell is not equal to 2, that means 'MAZE[N-1][N-1]' is reachable.
- Else return “NO”.