Walls and Gates

• 遇到搜索的题目的时候，不要直接开始套模板。而是应该分析要从什么呢地方开始搜索。
  • 例如这道题目，最好的办法并不是直接从每个点开始搜索，而是应该从gates出发，去更新临近的点。否则就会遇到不存在gates的情况。
• BFS和DFS都可以实现
  • BFS复杂度：O(mn) 注意bfs有两种实现方法
    1. 对每个gate都进行一次BFS
    2. 把所有的gate加到queue，只进行一次BFS，这样更简单因为只需要更新INF位置的值即可

int INF = Integer.MAX_VALUE;
public void wallsAndGates(int[][] rooms) {

    if (rooms.length == 0 || rooms[0].length == 0)
        return;
    Queue<Point> queue = new LinkedList<>();

    for (int i = 0; i < rooms.length; i++) {
        for (int j = 0; j < rooms[0].length; j++) {
            if (rooms[i][j] == 0)                
             queue.add(new Point(i, j));
        }
    }

    int[] deltaX = {1, 0, -1, 0};
    int[] deltaY = {0, 1, 0, -1};
    int distance = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            Point p = queue.poll();
            for (int j = 0; j < 4; j++) {
                int newX = p.x + deltaX[j];
                int newY = p.y + deltaY[j];
                if (newX < 0 || newY < 0 || newX > rooms.length - 1 || newY > rooms[0].length - 1 
                    || rooms[newX][newY] == -1)
                    continue;

                if (rooms[newX][newY] == INF) {
                    rooms[newX][newY] = distance + 1;
                    queue.add(new Point(newX, newY));
                }                                        
            }
        }
        distance++;
    }

}
private class Point {
    int x;
    int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }            
}

• DFS: 注意剪枝，当rooms[newX][newY] <= distance的时候不用继续向下搜索
  • 复杂度：

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

    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);                 
        }
    }

  private void dfs(int[][] rooms, int x, int y, int distance) {
        int[] deltaX = {1, 0, -1, 0};
        int[] deltaY = {0, 1, 0, -1};

        for (int j = 0; j < 4; j++) {
            int newX = x + deltaX[j];
            int newY = y + deltaY[j];
            if (newX < 0 || newY < 0 || newX > rooms.length - 1 || newY > rooms[0].length - 1 
                || rooms[newX][newY] == -1 || rooms[newX][newY] <= distance)
                continue;


            rooms[newX][newY] = distance + 1;
            dfs(rooms, newX, newY, distance + 1);                            
        }
    }