Shortest Distance in a Maze

Given a matrix of integers A of size N x M describing a maze. The maze consists of empty locations and walls.
1 represents a wall in a matrix and 0 represents an empty location in a wall.

There is a ball trapped in a maze. The ball can go through empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall.
When the ball stops, it could choose the next direction.

Given two array of integers of size B and C of size 2
denoting the starting and destination position of the ball.

Find the shortest distance for the ball to stop at the destination.
The distance is defined by the number of empty spaces traveled by the ball
from the starting position (excluded) to the destination (included).
If the ball cannot stop at the destination, return -1.

Note:

  1. Rows are numbered from top to bottom and columns are numbered from left to right.

  2. Assume the border of the maze are all walls.

  3. Both the starting position of the ball and the destination position of the ball exist on an empty space.

  4. Both the starting and destination positions will not be at the same position initially.



Input Format

The first argument given is the integer matrix A.
The second argument given is an array of integer B.
The third argument if an array of integer C.

Output Format

Return the shortest distance for the ball to stop at the destination. and if it impossible return -1 instead.

Constraints

2 <= N, M <= 100
0 <= A[i] <= 1
0 <= B[i][0], C[i][0] < N
0 <= B[i][1], C[i][1] < M

For Example

Input 1:
    A = [   [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]   ] 
    B = [0, 4]
    C = [4, 4]
Output 1:
    12
    Shortest path to the destination: left -> down -> left -> down -> right -> down -> right
    The total distance is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

Input 2:
    A = [   [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]  ]
    B = [0, 4]
    C = [3, 2]
    B = 3
Output 2:
    -1
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Shortest Distance in a Maze on Interview Code Editor
Sign Up
to access hints and editorial solutions for Shortest Distance in a Maze

Discussion


Loading...
Click here to start solving coding interview questions