Last Updated: 24 Nov, 2021
The Maze ll
Hard
Asked in companies
Ninja is stuck in a maze with empty spaces and walls. Ninja can go through empty spaces by running up, down, left or right, but he will continue running in the same direction until hitting a wall. When he stops, he could choose the next direction.
Given Ninja's start position, the destination and the maze, find the shortest distance for Ninja to stop at the destination. The distance is defined by the number of empty spaces traveled by Ninja from the start position (excluded) to the destination (included). If Ninja cannot stop at the destination, return -1.
The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.
Note :
Both Ninja’s starting cell and the destination cell exist on an empty space, and they will not be at the same position initially.
The given maze does not contain borders (like the red rectangle in the sample pictures), but you could assume the borders of the maze are all walls.
Example :
N = 3, M = 3
Maze = [ [ 0, 0, 0 ], [ 0, 1, 0 ], [ 1, 0, 0] ]
Start = [ 0, 0 ]
Destination = [ 2, 1 ]
Explanation :
Ninja can start from (0,0) and take the right direction and run till (0,2). Then he turns direction to down and runs till (2,2). Then Ninja turns direction to the left and runs till (2,1).
Input Format :
The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.
The first line of each test case contains integers ‘N’ and ‘M’ representing the number of rows and columns of the maze.
The next ‘N’ line contains ‘M’ integers representing the cells of the maze. 1 represents a wall and 0 represents the empty space.
The next line contains two integers representing the coordinates of the starting position of Ninja.
The next line contains the destination coordinates.
Output format :
For each test case, output an integer denoting the shortest distance required to reach from the starting position to the destination. If it is impossible to reach the destination, output -1.
Print the output of each test case in a new line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 100
1 <= M <= 100
Time Limit : 1 sec
Approaches
Approach :
- Since we need to find the shortest path in the maze, we will use BFS with priority queue.
- We will check all the four directions from the cell Ninja currently is on, and keep running until a wall is encountered.
- When we hit a blocking cell and if this cell was not visited before, we add it to the priority queue.
- This way, we can check all the reachable cells as well as the shortest distance required to reach them.
Algorithm :
- Initialise a 2-D array ‘dir’.
- For the left direction, ‘dir[0]’ = {0,-1}.
- For the right direction, ‘dir[1]’ = {0,1}.
- For the up direction, ‘dir[2]’ = {-1,0}.
- For the down direction, ‘dir[3]’ = {1,0}.
- Initialise a 2-D array ‘visited’ to mark the visited cells in the maze.
- Initialise a priority queue ‘q’ that stores the coordinates and the distance travelled to reach this cell.
- This priority queue prioritizes the shortest distance first.
- Add starting coordinates with distance ‘0’ to ‘q’.
- Run a while loop until ‘q’ is empty.
- Pop the top coordinates of ‘q’.
- Let the coordinates be ‘x’, ‘y’ and the distance be ‘d’.
- If this is the destination cell, return ‘d’.
- Mark the current cell as ‘visited’.
- Run a loop from ‘k=0’ to ‘k=3’ for all the four directions.
- Keep travelling in the same direction until a wall is reached.
- Let the new coordinates be ‘nx’ and ‘ny’.
- If ‘(nx,ny)’ is not visited, add the cell to ‘q’ along with the distance travelled.
- If we reach out of the priority queue, the cell is not reachable and we return -1.