Walls and Gates

Question

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.

Solution

這題只考基本的 BFS，當然可以選擇用 Queue 來做，但我選擇用 recursion，不過用 recursion 在 matrix 需要考慮到的是該怎麼限制它的走法。如果只是無腦的讓他上下左右走，其實會走回原點，也可能重複走，會產生 stackoverflow 的問題。其實只需要加一個 rooms[i][j] < level，就可以秒殺這一題。

我選擇用 boolean[][] visited 來記錄走過的點，但答案是錯的。為什麼呢？因為用 recursion 其實不算是真的 BFS，比較像是 DFS，要有好的限制條件才能變成 BFS。我下面那樣的寫法是錯的，錯就錯在像這種情形：

[I, I, 0, 0, I, I]

這樣會遇到一個問題，就是雖然從右上角的 0 開始走起，我預計在 0 的左邊跟下面的 I 要變成 1，但因為 recursion 加上 visited 並無法將它限制成 BFS，因此他可能會先走左邊的 I，然後往下，再走到右邊的 I，因此這個 I 等於 3。然後，我又把它的 visited 設為 true，因此他在從右上角 0 開始這輪就是 3。接著，左下角這個 0 開始 BFS，比較幸運，他直接往右走兩格，因此 Math.min 會將它變成 2。就是如此才導致錯誤的答案。以後做這種題目都要格外小心

    final int[][] steps = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.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) {
                    bfs(rooms, i, j, 0, new boolean[rooms.length][rooms[0].length]);
                }
            }
        }
        return;
    }

    public void bfs(int[][] rooms, int row, int col, int level, boolean[][] visited) {
        if (rooms[row][col] == -1) {
            return;
        }
        if (rooms[row][col] == Integer.MAX_VALUE) {
            rooms[row][col] = level;
        } else if (rooms[row][col] != Integer.MAX_VALUE && rooms[row][col] != 0) {
            rooms[row][col] = Math.min(rooms[row][col], level);
        }

        visited[row][col] = true;
        for (int[] step : steps) {
            int x = step[0] + row, y = step[1] + col;
            if (x < 0 || x >= rooms.length || y < 0 || y >= rooms[0].length || visited[x][y]) {
                continue;
            }
            bfs(rooms, x, y, level + 1, visited);
        }
        return;
    }

補上正解

    final int[][] steps = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.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) {
                    bfs(rooms, i, j, 0);
                }
            }
        }
        return;
    }

    public void bfs(int[][] rooms, int row, int col, int level) {
        if (row < 0 || row >= rooms.length || col < 0 || col >= rooms[0].length || rooms[row][col] < level) {
            return;
        }

        rooms[row][col] = level;
        for (int[] step : steps) {
            int x = step[0] + row, y = step[1] + col;
            bfs(rooms, x, y, level + 1);
        }
        return;
    }