描述
给出一个二维的网格，每一格可以代表墙 2 ，房子 1，以及空 0 (用数字0,1,2来表示)，在网格中找到一个位置去建立邮局，使得所有的房子到邮局的距离和是最小的。
返回所有房子到邮局的最小距离和，如果没有地方建立邮局，则返回-1.

• 你不能穿过房子和墙，只能穿过空地。
• 你只能在空地建立邮局。

在线评测地址：领扣题库官网

样例1
输入：[[0,1,0,0,0],[1,0,0,2,1],[0,1,0,0,0]]
输出：8
解释： 在(1,1)处建立邮局，所有房子到邮局的距离和是最小的。

样例2
输入：[[0,1,0],[1,0,1],[0,1,0]]
输出：4
解释：在(1,1)处建立邮局，所有房子到邮局的距离和是最小的。

考点：bfs

题解：

• 本题采用bfs，首次遍历网格，对空地处进行bfs，搜索完成后如果存在房屋没有被vis标记则改空地不可以设置房屋。
• 朴素的bfs搜索过程中，sun+=dist;实现当前点距离和的更新。

• now.dis+1每次实现当前两点间距离的更新。
  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;
  }
  
  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);
      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;
  }
  
  private void bfs(Coordinate start,
                   int[][] distanceSum,
                   int[][] visitedTimes) {
      Queue<Coordinate> queue = new LinkedList<>();
      boolean[][] hash = new boolean[n][m];
  
      queue.offer(start);
      hash[start.x][start.y] = true;
  
      int steps = 0;
      while (!queue.isEmpty()) {
          steps++;
          int size = queue.size();
          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;
                  distanceSum[adj.x][adj.y] += steps;
                  visitedTimes[adj.x][adj.y]++;
              } // direction
          } // for temp
      } // while
  }
  }

  //version 硅谷算法班
  public class Solution {
  /**
   * @param grid: a 2D grid
   * @return: An integer
   */
  public int shortestDistance(int[][] grid) {
      // write your code here
      if (grid == null || grid.length == 0 || grid[0].length == 0) {
          return -1;
      }
  
      int ans = Integer.MAX_VALUE;
  
      for (int i = 0; i < grid.length; i++) {
          for (int j = 0; j < grid[0].length; j++) {
              if (grid[i][j] == 0) {
                  ans = Math.min(ans, bfs(grid, i, j));
              }
          }
      }
      return ans == Integer.MAX_VALUE ? -1 : ans;
  }
  
  private int bfs(int[][] grid, int sx, int sy) {
      Queue<Integer> qx = new LinkedList<>();
      Queue<Integer> qy = new LinkedList<>();
      boolean[][] v = new boolean[grid.length][grid[0].length];
  
      qx.offer(sx);
      qy.offer(sy);
      v[sx][sy] = true;
  
      int[] dx = {1, -1, 0, 0};
      int[] dy = {0, 0, 1, -1};
  
      int dist = 0;
      int sum = 0;
  
      while (!qx.isEmpty()) {
          dist++;
          int size = qx.size();
          for (int i = 0; i < size; i++) {
              int cx = qx.poll();
              int cy = qy.poll();
              for (int k = 0; k < 4; k++) {
                  int nx = cx + dx[k];
                  int ny = cy + dy[k];
                  if (0 <= nx && nx < grid.length && 0 <= ny && ny < grid[0].length && !v[nx][ny]) {
                      v[nx][ny] = true;
  
                      if (grid[nx][ny] == 1) {
                          sum += dist;
                      }
                      if (grid[nx][ny] == 0) {
                          qx.offer(nx);
                          qy.offer(ny);
                      }
                  }
              }
          }
      }
  
      for (int i = 0; i < grid.length; i++) {
          for (int j = 0; j < grid[0].length; j++) {
              if (grid[i][j] == 1 && !v[i][j]) {
                  return Integer.MAX_VALUE;
              }
          }
      }
      return sum;
  }
  }

更多题解参考：九章官网solution