Given a matrix of integers A of size N x M consisting of values 0, 1, or 2.
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.