Shortest Distance from All Buildings

Given a matrix of integers A of size N x M consisting of values 0, 1, or 2.

  • 0 represents an empty land which you can pass by freely.
  • 1 represents a building which you cannot pass through.
  • 2 represents an obstacle which you cannot pass through.

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance.
You can only move up, down, left and right.

Find the shortest distance.
If it is not possible to build such a house according to the above rules, return -1.

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



Input Format

The only argument given is the integer matrix A.

Output Format

Return the shortest distance, If it is not possible to build such house according to the above rules, return -1.

Constraints

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

For Example

Input 1:
    A = [   [1, 0, 2, 0, 1]
            [0, 0, 0, 0, 0]
            [0, 0, 1, 0, 0]   ]
Output 1:
    7
    The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1 = 7 which is  minimal
    among all possible locations.

Input 2:
     A = [  [1, 0, 2, 0, 1]
            [2, 0, 0, 2, 0]
            [0, 2, 1, 0, 2]   ]
Output 2:
    -1
    It is not possible to build such a house on empty such that all buildings are reachable from it.
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 from All Buildings on Interview Code Editor
Sign Up
to access hints and editorial solutions for Shortest Distance from All Buildings

Discussion


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