Staff
Shortest Distance from All Buildings
You are given an m x n grid grid representing a city map where:
0represents an empty land cell.1represents a building.2represents an obstacle.
You may move from an empty land cell to another empty land cell in one step in one of four directions: up, down, left, or right. You cannot pass through buildings or obstacles.
Return the minimum total travel distance from an empty land cell to all buildings. If it is impossible to choose an empty land cell that can reach every building, return -1.
Example 1
1 0 2 0 1 0 0 0 0 0 0 0 1 0 0
Input
grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]Output
7The empty land at position (1, 2) has distances 3, 3, and 1 to the three buildings, for a total distance of 7.
Example 2
1 0
Input
grid = [[1,0]]Output
1The only empty land is adjacent to the only building, so the shortest total distance is 1.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 50
- grid[i][j] is either 0, 1, or 2
- There is at least one building in grid