阿裡面試真題詳解：郵局的建立 II

描述

給出一個二維的網格，每一格可以代表牆 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