Comment on page

# 317.Shortest-Distance-from-All-Buildings

## 题目描述

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. You are given a 2D grid of values 0, 1 or 2, where:
Each 0 marks an empty land which you can pass by freely.
Each 1 marks a building which you cannot pass through.
Each 2 marks an obstacle which you cannot pass through.
Example:
Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
1 - 0 - 2 - 0 - 1
| | | | |
0 - 0 - 0 - 0 - 0
| | | | |
0 - 0 - 1 - 0 - 0
Output: 7
Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2),
the point (1,2) is an ideal empty land to build a house, as the total
travel distance of 3+3+1=7 is minimal. So return 7.
Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

## 代码

### Approach #1 BFS

Time: O(M^2N^2) or O(E*MN) && Space: O(MN)
class Solution {
public int shortestDistance(int[][] grid) {
if (grid == null || grid.length = 0) return 0;
int[] shift = new int[] {0, 1, 0, -1, 0};
int row = grid.length;
int col = grid.length;
int[][] distance = new int[row][col];
int[][] reach = new int[row][col];
int buildingNum = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == 1) {
buildingNum++;
myQueue.offer(new int[]{i, j});
boolean[][] visited = new boolean[row][col];
int level = 1;
while (!myQueue.isEmpty()) {
int qSize = myQueue.size();
for (int q = 0; q < qSize; q++) {
int[] curr = myQueue.poll();
for (int k = 0; k < 4; k++) {
int nextRow = curr + shift[k];
int nextCol = curr + shifit[k+1];
if (nextRow >= 0 && nextRow < row && nextCol >= 0 && nextCol < col && grid[nextRow][nextCol] == 0 && !visited[nextRow][nextCol]) {
distance[nextRow][nextCol] += level;
reach[nextRow][nextCol]++;
visited[nextRow][nextCol] = true;
myQueue.offer(new int[] {nextRow, nextCol});
}
}
}
level++;
}
}
}
}
int shortest = Integer.MAX_VALUE;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == 0 && reach[i][j] == buildingNum) {
shortest = Math.min(shortest, distance[i][j]);
}
}
}
return shortest == Integer.MAX_VALUE ? -1 : shortest;
}
}