描述
给出一个二维的网格，每一格可以代表墙 2 ，房子 1，以及空 0 (用数字0,1,2来表示)，在网格中找到一个位置去建立邮局，使得所有的房子到邮局的距离和是最小的。
返回所有房子到邮局的最小距离和，如果没有地方建立邮局，则返回-1.
注意事项
你不能穿过房子和墙，只能穿过空地。
你只能在空地建立邮局。
您在真实的面试中是否遇到过这个题？ Yes
样例
给出一个网格：
0 1 0 0 0
1 0 0 2 1
0 1 0 0 0
返回 8，你可以在(1,1)处建立邮局 (在(1,1)处建立邮局，所有房子到邮局的距离是最近的)。
挑战
在O(n^3)内的时间复杂度解决此问题。
代码
class Coordinate {
int x, y;
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Solution {
public int EMPTY = 0;
public int HOUSE = 1;
public int WALL = 2;
public int[][] grid;
public int n, m;
public int[] deltaX = {0, 1, -1, 0};
public int[] deltaY = {1, 0, 0, -1};
// 得到网格中所有给定类型的位置坐标
private List<Coordinate> getCoordinates(int type) {
List<Coordinate> coordinates = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == type) {
coordinates.add(new Coordinate(i, j));
}
}
}
return coordinates;
}
// setGrid方法可以将二维网格的值传递给全局变量grid，m，n
// 这样不必每个方法都传递这三个形参
private void setGrid(int[][] grid) {
n = grid.length;
m = grid[0].length;
this.grid = grid;
}
private boolean inBound(Coordinate coor) {
if (coor.x < 0 || coor.x >= n) {
return false;
}
if (coor.y < 0 || coor.y >= m) {
return false;
}
return grid[coor.x][coor.y] == EMPTY;
}
/**
* @param grid a 2D grid
* @return an integer
*/
public int shortestDistance(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return -1;
}
// set n, m, grid
setGrid(grid);
List<Coordinate> houses = getCoordinates(HOUSE);
// 初始化时distanceSum和visitedTimes直接被设为0；
int[][] distanceSum = new int[n][m];
int[][] visitedTimes = new int[n][m];;
for (Coordinate house : houses) {
bfs(house, distanceSum, visitedTimes);
}
int shortest = Integer.MAX_VALUE;
List<Coordinate> empties = getCoordinates(EMPTY);
for (Coordinate empty : empties) {
// 若出现下列情况说明空点被房子阻碍了，不能到达所有房子的点不需要
if (visitedTimes[empty.x][empty.y] != houses.size()) {
continue;
}
shortest = Math.min(shortest, distanceSum[empty.x][empty.y]);
}
// 可能没有一块空地可以到达所有房子
if (shortest == Integer.MAX_VALUE) {
return -1;
}
return shortest;
}
/* bfs遍历的是所有房子，bfs过程得到了每块空地到所有它能到达的房子的距离总和
* 以及每块空地能被多少个房子访问
*/
private void bfs(Coordinate start,
int[][] distanceSum,
int[][] visitedTimes) {
Queue<Coordinate> queue = new LinkedList<>();
// hash用于去重
boolean[][] hash = new boolean[n][m];
queue.offer(start);
hash[start.x][start.y] = true;
/* bfs中必须要有对steps = 0 的初始化，因为每次bfs都要把steps重置为0，
* 不然从另外的点开始bfs，step还是上次的，就会出bug
*/
int steps = 0;
while (!queue.isEmpty()) {
// 分层遍历，每算完队列中的一层数steps更新一次
steps++;
int size = queue.size();
// 如果不分层遍历，队列每poll一个坐标，steps就会更新一次，实际上应该是将一层元素poll完后steps才更新
// 在分层遍历时，队列要在层的for循环中poll坐标，不然就会出现重复size次遍历当前poll的坐标的相邻四个坐标，结果必然是错误的
for (int temp = 0; temp < size; temp++) {
Coordinate coor = queue.poll();
for (int i = 0; i < 4; i++) {
Coordinate adj = new Coordinate(
coor.x + deltaX[i],
coor.y + deltaY[i]
);
if (!inBound(adj)) {
continue;
}
// 访问过的点就不要再访问了
if (hash[adj.x][adj.y]) {
continue;
}
queue.offer(adj);
hash[adj.x][adj.y] = true;
// 多个house到同一片空地的距离累加
distanceSum[adj.x][adj.y] += steps;
// 对每个house而言，每个空地只会访问一次
// visitedTimes记录的是每个空地被访问的总次数
visitedTimes[adj.x][adj.y]++;
}
}
}
}
}
出bug的一个地方：
代码
bfs中的本该存在的steps = 0初始化写到了20行的public int steps = 0位置;出现了bug，原因是steps表示空地到当前传入house的位置的距离，在bfs中应存在对steps = 0的初始化，每传入一个house的位置，steps必须初始化为0；若将steps设为全局变量，则下一个house位置的steps是在上一个house的steps的基础上计算的
输出
