题目地址：

https://leetcode.com/problems/shortest-distance-from-all-buildings/

给定一个二维矩阵，只含$0,1,2$，$0$代表空地，$1$代表建筑，$2$代表障碍物。要求在一个空地建个房屋，使得房屋到所有建筑物的路径长度之和达到最小。路径的每一步只能向上下左右走，并且只能走到空地上。如果存在房屋的建造方案，则返回最短路径长度总和；否则返回$-1$。

思路是BFS。可以从每个建筑物出发，遍历一下其所能到达的空地，并累加该空地与之的路径距离。遍历的同时要注意，如果一个某个空地这个建筑物到不了，那么说明这个空地是不能建房屋的，最后统计的时候要把这个空地排除在外。代码如下：

import java.util.LinkedList; import java.util.Queue; public class Solution { public int shortestDistance(int[][] grid) { int m = grid.length, n = grid[0].length; // totalDis存每个空地到其余所有建筑的距离之和 int[][] totalDis = new int[m][n]; // 遍历所有的建筑，累加其能到达的空地与之的距离 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { bfs(i, j, grid, totalDis); } } } // 找一下能到达所有建筑物的空地中，哪个空地与所有建筑物的距离和最小 int res = Integer.MAX_VALUE; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 0 && totalDis[i][j] != -1) { res = Math.min(res, totalDis[i][j]); } } } // 如果没找到，返回-1；否则返回答案 return res == Integer.MAX_VALUE ? -1 : res; } private void bfs(int x, int y, int[][] grid, int[][] totalDis) { Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{x, y}); int[] d = {1, 0, -1, 0, 1}; // 记录能够到达的空地 boolean[][] visited = new boolean[grid.length][grid[0].length]; // 记录步数 int step = 0; while (!queue.isEmpty()) { step++; // 分层遍历要记录size int size = queue.size(); for (int i = 0; i < size; i++) { int[] cur = queue.poll(); for (int j = 0; j < 4; j++) { int nextX = cur[0] + d[j], nextY = cur[1] + d[j + 1]; if (inBound(nextX, nextY, grid) && !visited[nextX][nextY] && grid[nextX][nextY] == 0) { visited[nextX][nextY] = true; if (totalDis[nextX][nextY] != -1) { totalDis[nextX][nextY] += step; } int[] next = {nextX, nextY}; queue.offer(next); } } } } // 标记一下未遍历到的空地，该空地最后不能参与统计 for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == 0 && !visited[i][j]) { totalDis[i][j] = -1; } } } } private boolean inBound(int x, int y, int[][] grid) { return 0 <= x && x < grid.length && 0 <= y && y < grid[0].length; } }

时间复杂度$O(kmn)$，$k$为建筑物数量，空间$O(mn)$。