Medium

Do I really know what I was doing the first I do this problem?
Hell no!
Checked the answer again and started to get the feel of BFS.
這道題有個地方有點卡，就是為什么用BFS就確定每次遇到INF的點之后，第一次更新的距離就是離Gate的最近距離呢. 為什么有此疑問呢，因為我認為到INF的Gate可以有好多個，那么我們第一次check == ? INF時更新的那個INF to Gate的distance可能并不是最近的呀，那我們之后想要update的話怎么辦呢，畢竟我們BFS的判斷條件是==?INF呀，更新過后就是普通int了，所以看起來永遠無法更新。然而事實就是不需要更新。

I had the same doubt as this person:

I don't see how this makes sure the shortest distance is found!
Once a room is discovered, it will not be traversed again (the == INF check), and thus will never get updated. What am I missing?

某個人解釋得很好：

Here's my understanding of why this solution guarantees the shortest distance.
We can understand it by level-order BFS.
First we put all 0s to a queue, let's say these these 0s are in level 1. Then from each 0 of the queue, we will go up, down, left and right, all these positions that are rooms are at level 1, and so forth. So assume we only have Gate A and Gate B, and we have a room C and all the other positions are walls. Assume that distance between AC is 3 and distance between BC is 4. So for Gate A, room C is at its level 3, for Gate B, room C is at its level 4. Since we are doing level-order BFS, so C will always first be accessed by the gate that is closer to it, so it will be A.

Straightforwad的代碼：

class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0].length == 0){
            return;
        }
        int m = rooms.length;
        int n = rooms[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (rooms[i][j] == 0){
                    queue.offer(new int[]{i,j});
                }
            }
        }
        while (!queue.isEmpty()){
            int[] top = queue.poll();
            int row = top[0];
            int col = top[1];
            if (row > 0 && col < n && rooms[row - 1][col] == Integer.MAX_VALUE){
                rooms[row - 1][col] = rooms[row][col] + 1; 
                queue.offer(new int[]{row - 1, col});
            }
            if (row + 1 < m && col < n && rooms[row + 1][col] == Integer.MAX_VALUE){
                rooms[row + 1][col] = rooms[row][col] + 1; 
                queue.offer(new int[]{row + 1, col});
            }
            if (col > 0 && rooms[row][col - 1] == Integer.MAX_VALUE){
                rooms[row][col - 1] = rooms[row][col] + 1;
                queue.offer(new int[]{row, col - 1});
            }
            if (col + 1 < n && col < n && rooms[row][col + 1] == Integer.MAX_VALUE){
                rooms[row][col + 1] = rooms[row][col] + 1;
                queue.offer(new int[]{row, col + 1});
            }
        }
    }
}