The Maze ll

Hard
0/120
Average time to solve is 25m
profile
Contributed by
10 upvotes
Asked in companies
SAP LabsAmazon

Problem statement

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).
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
5 5
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
0 4 
4 4
Sample Output 1 :
12
Explanation Of Sample Input 1 :
For test case 1 we have, 


The starting position is (0,4) and the destination is (4,4).

One of the shortest ways is : left -> down -> left -> down -> right -> down -> right.

The total distance is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

So, we output 12.
Sample Input 2 :
2
3 4
1 0 1 0 
0 0 0 1 
0 0 1 1 
2 1
1 2
3 5
0 0 0 1 0 
0 1 1 1 1 
1 1 0 0 0 
2 4
0 0
Sample Output 2 :
4
-1
Hint

Think of the BFS approach.

 

Approaches (1)
Optimal Approach

 

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.

 

Time Complexity

O( N*M*Max(N,M) ) , where ‘N’ is the number of rows and ‘M’ is the number of columns in the maze. 
 

We are checking each cell of the maze until we reach the destination and for each cell we can travel a maximum of (M,N) cells , so the overall time complexity is O( N*M*Max(N,M) ).
 

Space Complexity

O(N*M)

 

We are maintaining a 2-D array to mark the visited cells. Hence, the overall Space Complexity is O(N*M).
 

Code Solution
(100% EXP penalty)
The Maze ll
Full screen
Console