摘要：題目鏈接這道題感覺是那道的簡化版，思路都是一樣的。是把所有的點都先放到里面，然后一起遍歷。這種寫法的好處是保證了每個點都只被放進一次，不會重復遍歷。保證了時間復雜是。可以不寫成層次遍歷的形式，直接，的程序

題目鏈接：https://leetcode.com/problems...

這道題感覺是那道“Shortest Distance from All Buildings”的簡化版，思路都是一樣的。鏈接：https://segmentfault.com/a/11...

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        /* bfs for each gates, room[i][j] = distance from (i, j) to gate
         * update room[i][j] each time 
         * bfs: 1. q and level 
         *      2. go over current level
         *         if (x, y) is in matrix && empty && room[x][y] > level
         *         - room[x][y] = level 
         *         - q.offer(x, y)
         */
         
         for(int i = 0; i < rooms.length; i++) {
             for(int j = 0; j < rooms[0].length; j++) {
                 if(rooms[i][j] == 0) bfs(rooms, i, j);
             }
         }
    }
    
    int[] dx = new int[] {-1, 1, 0, 0};
    int[] dy = new int[] {0, 0, -1, 1};
    private void bfs(int[][] rooms, int x, int y) {
        Queue q = new LinkedList();
        q.offer(new int[] {x, y});
        int level = 0;
        // 1. bfs loop use a queue
        while(!q.isEmpty()) {
            level++;
            // 2. go over current level
            for(int j = q.size(); j > 0; j--) {
                int[] cur = q.poll();
                // 4 directions
                for(int i = 0; i < 4; i++) {
                    int nx = cur[0] + dx[i], ny = cur[1] + dy[i];
                    // if (x, y) is in matrix && empty && room[x][y] > level
                    if(nx >= 0 && nx < rooms.length && ny >= 0 && ny < rooms[0].length && rooms[nx][ny] > level) {
                        rooms[nx][ny] = level;
                        q.offer(new int[] {nx, ny});
                    }
                }
            }
        }
    }
}

看到discussion里面bfs還有一種寫法。是把所有gates的點都先放到q里面，然后一起遍歷。這種寫法的好處是：保證了每個點都只被放進q一次，不會重復遍歷。保證了時間復雜是O(MN), M = rooms.length, N = rooms[0].length。

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        /* bfs */
        Queue q = new LinkedList();
        for(int i = 0; i < rooms.length; i++) {
            for(int j = 0; j < rooms[0].length; j++) {
                if(rooms[i][j] == 0) q.offer(new int[] {i, j});
            }
        }
        bfs(rooms, q); 
    }
    
    int[] dx = new int[] {-1, 1, 0, 0};
    int[] dy = new int[] {0, 0, -1, 1};
    private void bfs(int[][] rooms, Queue q) {
        int level = 0;
        while(!q.isEmpty()) {
            level++;
            for(int j = q.size(); j > 0; j--) {
                int[] cur = q.poll();
                // 4 directions
                for(int i = 0; i < 4; i++) {
                    int nx = cur[0] + dx[i], ny = cur[1] + dy[i];
                    if(nx >= 0 && nx < rooms.length && ny >= 0 && ny < rooms[0].length && rooms[nx][ny] > level) {
                        rooms[nx][ny] = level;
                        q.offer(new int[] {nx, ny});
                    }
                }
            }
        }
    }
}

可以不寫成層次遍歷的形式，直接bfs，level = poll + 1：

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        /* bfs */
        Queue q = new LinkedList();
        for(int i = 0; i < rooms.length; i++) {
            for(int j = 0; j < rooms[0].length; j++) {
                if(rooms[i][j] == 0) q.offer(new int[] {i, j});
            }
        }
        bfs(rooms, q); 
    }
    
    int[] dx = new int[] {-1, 1, 0, 0};
    int[] dy = new int[] {0, 0, -1, 1};
    private void bfs(int[][] rooms, Queue q) {
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];
            // 4 directions
            for(int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i], ny = cur[1] + dy[i];
                if(nx >= 0 && nx < rooms.length && ny >= 0 && ny < rooms[0].length && rooms[nx][ny] > rooms[x][y] + 1) {
                    rooms[nx][ny] = rooms[x][y] + 1;
                    q.offer(new int[] {nx, ny});
                }
            }
            
        }
    }
}

dfs的程序：

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        /* dfs */
         for(int i = 0; i < rooms.length; i++) {
             for(int j = 0; j < rooms[0].length; j++) {
                 if(rooms[i][j] == 0) dfs(rooms, i, j, 0);
             }
         }
    }
    
    int[] dx = new int[] {-1, 1, 0, 0};
    int[] dy = new int[] {0, 0, -1, 1};
    private void dfs(int[][] rooms, int x, int y, int depth) {
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 0 && nx < rooms.length && ny >= 0 && ny < rooms[0].length && rooms[nx][ny] > depth + 1) {
                rooms[nx][ny] = depth + 1;
                dfs(rooms, nx, ny, depth + 1);
            }
        }
    }
}