摘要：廣度優(yōu)先搜索復(fù)雜度時(shí)間空間思路實(shí)際上就是找每個(gè)房間到最近的門(mén)的距離，我們從每個(gè)門(mén)開(kāi)始，廣度優(yōu)先搜索并記錄層數(shù)就行了。這題要注意剪枝，如果下一步是門(mén)或者下一步是墻或者下一步已經(jīng)訪問(wèn)過(guò)了，就不要加入隊(duì)列中。

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.


For example, given the 2D grid:
INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF 
After running your function, the 2D grid should be:
  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

時(shí)間 O(NM) 空間 O(N)

實(shí)際上就是找每個(gè)房間到最近的門(mén)的距離，我們從每個(gè)門(mén)開(kāi)始，廣度優(yōu)先搜索并記錄層數(shù)就行了。如果某個(gè)房間之前被標(biāo)記過(guò)距離，那就選擇這個(gè)距離和當(dāng)前距離中較小的那個(gè)。這題要注意剪枝，如果下一步是門(mén)或者下一步是墻或者下一步已經(jīng)訪問(wèn)過(guò)了，就不要加入隊(duì)列中。否則會(huì)超時(shí)。

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        if(rooms.length == 0) return;
        for(int i = 0; i < rooms.length; i++){
            for(int j = 0; j < rooms[0].length; j++){
                // 如果遇到一個(gè)門(mén)，從門(mén)開(kāi)始廣度優(yōu)先搜索，標(biāo)記連通的節(jié)點(diǎn)到自己的距離
                if(rooms[i][j] == 0) bfs(rooms, i, j);
            }
        }
    }
    
    public void bfs(int[][] rooms, int i, int j){
        Queue queue = new LinkedList();
        queue.offer(i * rooms[0].length + j);
        int dist = 0;
        // 用一個(gè)集合記錄已經(jīng)訪問(wèn)過(guò)的點(diǎn)
        Set visited = new HashSet();
        visited.add(i * rooms[0].length + j);
        while(!queue.isEmpty()){
            int size = queue.size();
            // 記錄深度的搜索
            for(int k = 0; k < size; k++){
                Integer curr = queue.poll();
                int row = curr / rooms[0].length;
                int col = curr % rooms[0].length;
                // 選取之前標(biāo)記的值和當(dāng)前的距離的較小值
                rooms[row][col] = Math.min(rooms[row][col], dist);
                int up = (row - 1) * rooms[0].length + col;
                int down = (row + 1) * rooms[0].length + col;
                int left = row * rooms[0].length + col - 1;
                int right = row * rooms[0].length + col + 1;
                if(row > 0 && rooms[row - 1][col] > 0 && !visited.contains(up)){
                    queue.offer(up);
                    visited.add(up);
                }
                if(col > 0 && rooms[row][col - 1] > 0 && !visited.contains(left)){
                    queue.offer(left);
                    visited.add(left);
                }
                if(row < rooms.length - 1 && rooms[row + 1][col] > 0 && !visited.contains(down)){
                    queue.offer(down);
                    visited.add(down);
                }
                if(col < rooms[0].length - 1 && rooms[row][col + 1] > 0 && !visited.contains(right)){
                    queue.offer(right);
                    visited.add(right);
                }
            }
            dist++;
        }
    }
}