Walls And Gates

• Medium
• keyword: BFS
• 类似: Flood fill

You are given a m x n 2D grid initialized with these three possible values.

• -1 : A wall or an obstacle.
• 0 : A gate.
• INF : Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
• Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

idea1: BFS模版

• 一看就是典型的BFS问题, 和islands一样. 但是我第一次写居然在最后一个test case过不了了.
• 我的思路是: 对于每一个gate, call一次bfs, 如果该点正数的点(即已经update过距离的room), 就判断当下的BFS是否能有更近的距离, 若是, 则update, 否则就不对这个点BFS了.
• 然后参考了: Ethan Li的博客, 发现思路一样, 都是使用的BFS模版, 但是他的就过了. 主要在于直接保存的int[]到visited set和queue里面吧.
• 代码如下, 关键在于step什么时候更新(在该层结束后), queue什么时候poll/offer?

public void wallsAndGates(int[][] rooms) {
 if (rooms == null || rooms.length == 0) return;
 int M = rooms.length, N = rooms[0].length;
 for (int i = 0; i < M; ++i) {
   for (int j = 0; j < N; ++j) {
     if (rooms[i][j] == 0) {
       bfs(rooms, M, N, i, j);
     }
   }
 }
}

private void bfs(int[][] rooms, int M, int N, int i, int j) {
 Queue<int[]> q = new LinkedList<>();
 Set<int[]> visited = new HashSet<>();
 q.offer(new int[] {i, j});
 visited.add(new int[] {i, j});
 int step = 0;
 while (!q.isEmpty()) {
   int sz = q.size();
   step++;
   for (int lvl = 0; lvl < sz; ++lvl) {
     int[] rc = q.poll();
     int r = rc[0];
     int c = rc[1];
     for (int d = 0; d < 4; ++d) {
       int rr = r + dd[d][0];
       int cc = c + dd[d][1];
       if (isValid(rooms, M, N, rr, cc) && !visited.contains(
             new int[] {rr, cc})) {  // check boundary, wall, gates, visited
         if (rooms[rr][cc] > step) {
           rooms[rr][cc] = step;
           q.offer(new int[] {rr, cc});
           visited.add(new int[] {rr, cc});
         }
       }
     }
   }
 }
}

private boolean isValid(int[][] rooms, int M, int N, int r, int c) {
 if (r < 0 || r >= M || c < 0 || c >= N
   || rooms[r][c] == 0 || rooms[r][c] == -1
   ) {
   return false;
}
return true;
}

idea2: flood fill的同时进行!!! 看看这种BFS

• 然后我看了discuss, 发现了最好的方法: BFS的本质是queue来保证同一层的node"同时"update, 保证了每个node的neighbors可以有相同的值, 即每一层的邻居都是该层+1. 这是我以前没有想过的, 我上了九章之后就拘泥于九章的BFS模版了, 做题之前都没有好好思考了.
• 这里可以通过思考flood fill. 即一个图上有几个0, 其他都是INF, 然后看不断fill, 而且每次fill的值就是层数, 层层加一. 就知道这个算法的正确性了.
• 好处是什么? 这是严格的O(M*N), 因为所有点都是有且只有1次地update. 而且不需要visited set来判断. 因为每次update都是上一层来加一, 从而保证了所有点都是按照距离门的distance来加一, 相当于从门开始flood fill.
• 非常漂亮的解决了问题. 参考这个flooding的顺序: , 注意它的1,2,3确实是按顺序的.
• 代码如下

int[][] dd = new int[][] {
  {0, 1},
  {1, 0},
  {-1, 0},
  {0, -1}
};

public void wallsAndGates(int[][] rooms) {
  if (rooms == null || rooms.length == 0 || rooms[0].length == 0) return;
  Queue<int[]> q = new LinkedList<>();
  int M = rooms.length, N = rooms[0].length;
  for (int i = 0; i < M; ++i) {
    for (int j = 0; j < N; ++j) {
      if (rooms[i][j] == 0) {
        q.offer(new int[] {i, j});  //先把所有门都放入queue里
      }
    }
  }

  while (!q.isEmpty()) {  // 看看这个BFS和模版的区别
    int[] pop = q.poll();
    for (int i = 0; i < 4; ++i) {
      int rr = pop[0] + dd[i][0];
      int cc = pop[1] + dd[i][1];
      if (rr < 0 || rr >= M || cc < 0 || cc >= N || rooms[rr][cc] != Integer.MAX_VALUE) {
        continue;
      }
        rooms[rr][cc] = rooms[pop[0]][pop[1]] + 1;  // key point
        q.offer(new int[] {rr, cc});
      }
    }
  }