矩阵BFS，搜索最短距离

Walls and Gates 这题matrix里的点的起始状态只有3个，0:gate, -1:wall和int_max: 待搜索的路线。我一开始的做法是，遍历矩阵，每当碰到一个为0的点，就说了我走到了一个gate上，然后从这个gate开始做BFS，把不等于-1的点的距离如果能更新，就更新了。

看了别人的解以后，感觉自己对BFS的理解还是不够深刻，其实只要是从BFS开始搜，搜到的点，就一定是shortest distance，因此就谈不上更新一步了。所以更好的做法是先把所有的matrix[i][j]等于0的点都放到queue里去。每次进去queue后，先得到当前queue的size，在这个size以内，把我能遍历到的下一个值等于int_max的点，更新为current distance + 1，并且放到下一轮的queue中去。

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0) {
            return;
        }

        int m = rooms.length, n = rooms[0].length;
        Queue<int[]> queue = new LinkedList<int[]>();
        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});
                }
            }
        }

        final int[] dx = {-1, 1, 0, 0};
        final int[] dy = {0, 0, -1, 1};

        int distance = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int l = 0; l < size; l++) {
                int[] pos = queue.poll();
                int i = pos[0], j = pos[1];
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && rooms[x][y] == Integer.MAX_VALUE) {
                        rooms[x][y] = distance;
                        queue.offer(new int[]{x, y});
                    } 
                }                
            }
            distance++;
        }
    }
}

Shortest Distance from All Buildings，建一个class叫Pair，有distace去记录更新每一个building到这个点距离，有visited_times去记录有多少个building曾经visit过这个点。每一次搜到一个grid[i][j]等于1的点，就做一个bfs，在bfs更新pair_grid里的值。最后把pair_grid里面，visited_times等于house number的点的最小的distance给return了。

public class Solution {

    private final int[] dx = {-1, 1, 0, 0};
    private final int[] dy = {0, 0, -1, 1};

    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return -1;
        }

        int m = grid.length, n = grid[0].length;
        Pair[][] pair_grid = new Pair[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                pair_grid[i][j] = new Pair();
            }
        }

        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    count++;
                    bfs(pair_grid, grid, i, j, new boolean[m][n]);
                }
            }
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 && pair_grid[i][j].visited == count) {
                    min = Math.min(min, pair_grid[i][j].distance);
                }
            }
        }

        return min == Integer.MAX_VALUE ? -1 : min;
    }

    private void bfs(Pair[][] pair_grid, int[][] grid, int i, int j, boolean[][] visited) {
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{i, j});
        int distance = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int m = 0; m < size; m++) {
                int[] pos = queue.poll();
                int x = pos[0], y = pos[1];
                for (int k = 0; k < 4; k++) {
                    int x2 = x + dx[k], y2 = y + dy[k];
                    if (x2 >= 0 && x2 < grid.length && y2 >= 0 && y2 < grid[0].length && !visited[x2][y2] && grid[x2][y2] == 0) {
                        visited[x2][y2] = true;
                        pair_grid[x2][y2].distance += distance;
                        pair_grid[x2][y2].visited++;
                        queue.offer(new int[]{x2, y2});
                    }
                }
            }
            distance++;
        }
    }
}

class Pair {
    int distance;
    int visited;

    public Pair() {
        distance = 0;
        visited = 0;
    }
}