leetcode 130的DFS解法

Question

bobo老师，我用DFS解决了lc 130 (https://leetcode.com/problems/surrounded-regions/) 问题。思路是先DFS遍历所有边界节点为'O'的字符，染色为true。最后简单遍历整个board, 把剩余的'O'重新赋值为'X' （代码如下）。成功提交后，我又回头看您的参考代码（https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0130-Surrounded-Regions/cpp-0130/main.cpp），您在文中说DFS可能会有问题，系统栈开销过大，所以用BFS。所以请教下，我的DFS成功提交，是不是说明DFS应该可行？

class Solution {
    private boolean[][] visited;
    private final int[] dx = {1, 0, -1, 0};
    private final int[] dy = {0, 1, 0, -1};
    private char[][] board;
    
    public void solve(char[][] board) {
        this.board = board;
        
        int m = board.length;
        int n = board[0].length;
        
        visited = new boolean[m][n];
        
        for (int i = 0; i < m; i ++) {
            if (!visited[i][0] && board[i][0] == 'O'){
                dfs(i, 0);
            }
            if (!visited[i][n - 1] && board[i][n - 1] == 'O') {
                dfs(i, n - 1);
            }
        }
        
        for (int j = 0; j < n; j ++) {
            if (!visited[0][j] && board[0][j] == 'O') {
                dfs(0, j);
            }
            if (!visited[m - 1][j] && board[m - 1][j] == 'O') {
                dfs(m - 1, j);
            }
        }
        
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (!visited[i][j] && board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
        
    }
    
    private void dfs(int x, int y) {
        
        visited[x][y] = true;
        
        
        for (int i = 0; i < 4; i ++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            
            if (inArea(xx, yy) && !visited[xx][yy] && board[xx][yy] == 'O') {
                dfs(xx, yy);
            }
        }
    }
    
    private boolean inArea(int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
    }
}

Answer 1

liuyubobobo 2022-03-28 02:25:18

Leetcode 的 C++ 的编译环境有过升级，现在 dfs 是 ok 的。

继续加油！：）

• 提问者 讲武德的年轻人 #1

  非常感谢！