{"id":299663,"date":"2021-01-17T21:42:00","date_gmt":"2021-01-17T13:42:00","guid":{"rendered":"http:\/\/4563.org\/?p=299663"},"modified":"2021-01-17T21:42:00","modified_gmt":"2021-01-17T13:42:00","slug":"%e8%b0%b7%e6%ad%8c%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%9a%e9%82%ae%e5%b1%80%e7%9a%84%e5%bb%ba%e7%ab%8b-ii","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=299663","title":{"rendered":"\u8c37\u6b4c\u9762\u8bd5\u9898\uff1a\u90ae\u5c40\u7684\u5efa\u7acb II"},"content":{"rendered":"
\n
\n
\n

\u8c37\u6b4c\u9762\u8bd5\u9898\uff1a\u90ae\u5c40\u7684\u5efa\u7acb II <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : zzzrf <\/span> <\/i> 5<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n

\u63cf\u8ff0<\/h3>\n

\u7ed9\u51fa\u4e00\u4e2a\u4e8c\u7ef4\u7684\u7f51\u683c\uff0c\u6bcf\u4e00\u683c\u53ef\u4ee5\u4ee3\u8868\u5899 2\uff0c\u623f\u5b50 1\uff0c\u4ee5\u53ca\u7a7a 0 (\u7528\u6570\u5b57 0,1,2 \u6765\u8868\u793a)\uff0c\u5728\u7f51\u683c\u4e2d\u627e\u5230\u4e00\u4e2a\u4f4d\u7f6e\u53bb\u5efa\u7acb\u90ae\u5c40\uff0c\u4f7f\u5f97\u6240\u6709\u7684\u623f\u5b50\u5230\u90ae\u5c40\u7684\u8ddd\u79bb\u548c\u662f\u6700\u5c0f\u7684\u3002<\/p>\n

\u8fd4\u56de\u6240\u6709\u623f\u5b50\u5230\u90ae\u5c40\u7684\u6700\u5c0f\u8ddd\u79bb\u548c\uff0c\u5982\u679c\u6ca1\u6709\u5730\u65b9\u5efa\u7acb\u90ae\u5c40\uff0c\u5219\u8fd4\u56de-1.<\/p>\n

    \n
  • \u4f60\u4e0d\u80fd\u7a7f\u8fc7\u623f\u5b50\u548c\u5899\uff0c\u53ea\u80fd\u7a7f\u8fc7\u7a7a\u5730\u3002<\/li>\n
  • \u4f60\u53ea\u80fd\u5728\u7a7a\u5730\u5efa\u7acb\u90ae\u5c40\u3002<\/li>\n<\/ul>\n

    \u5728\u7ebf\u8bc4\u6d4b\u5730\u5740<\/p>\n

    \u6837\u4f8b 1<\/h3>\n
    \u8f93\u5165\uff1a[[0,1,0,0,0],[1,0,0,2,1],[0,1,0,0,0]] \u8f93\u51fa\uff1a8 \u89e3\u91ca\uff1a \u5728(1,1)\u5904\u5efa\u7acb\u90ae\u5c40\uff0c\u6240\u6709\u623f\u5b50\u5230\u90ae\u5c40\u7684\u8ddd\u79bb\u548c\u662f\u6700\u5c0f\u7684\u3002 <\/code><\/pre>\n
    \u6837\u4f8b 2<\/h3>\n
    \u8f93\u5165\uff1a[[0,1,0],[1,0,1],[0,1,0]] \u8f93\u51fa\uff1a4 \u89e3\u91ca\uff1a\u5728(1,1)\u5904\u5efa\u7acb\u90ae\u5c40\uff0c\u6240\u6709\u623f\u5b50\u5230\u90ae\u5c40\u7684\u8ddd\u79bb\u548c\u662f\u6700\u5c0f\u7684\u3002 <\/code><\/pre>\n
    \u8003\u70b9\uff1abfs<\/p>\n
    \u9898\u89e3\uff1a<\/h3>\n
      \n
    • \u672c\u9898\u91c7\u7528 bfs\uff0c\u9996\u6b21\u904d\u5386\u7f51\u683c\uff0c\u5bf9\u7a7a\u5730\u5904\u8fdb\u884c bfs\uff0c\u641c\u7d22\u5b8c\u6210\u540e\u5982\u679c\u5b58\u5728\u623f\u5c4b\u6ca1\u6709\u88ab vis \u6807\u8bb0\u5219\u6539\u7a7a\u5730\u4e0d\u53ef\u4ee5\u8bbe\u7f6e\u623f\u5c4b\u3002<\/li>\n
    • \u6734\u7d20\u7684 bfs \u641c\u7d22\u8fc7\u7a0b\u4e2d\uff0csun+=dist;\u5b9e\u73b0\u5f53\u524d\u70b9\u8ddd\u79bb\u548c\u7684\u66f4\u65b0\u3002<\/li>\n
    • now.dis+1 \u6bcf\u6b21\u5b9e\u73b0\u5f53\u524d\u4e24\u70b9\u95f4\u8ddd\u79bb\u7684\u66f4\u65b0\u3002<\/li>\n<\/ul>\n
      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 \u7845\u8c37\u7b97\u6cd5\u73ed 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;     } } <\/code><\/pre>\n
      \u66f4\u591a\u9898\u89e3\u53c2\u8003<\/p>\n<\/p><\/div>\n
       \u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (0<\/span>)        <\/div>\n
       <\/div>\n<\/p><\/div>\n<\/p><\/div>\n
        \n
      • \n","protected":false},"excerpt":{"rendered":"
        \u8c37\u6b4c\u9762\u8bd5\u9898\uff1a\u90ae\u5c40\u7684\u5efa\u7acb II \u8cc7\u6df1…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/299663"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=299663"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/299663\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=299663"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=299663"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=299663"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}