讨论/《深度优先搜索》 - 练习:被围绕的区域/
《深度优先搜索》 - 练习:被围绕的区域
共 2 个回复
class Solution {
public:
    void dfs(vector<vector<char>>& board, int i, int j, vector<vector<bool>>& visited){
        int m=board.size();
        int n=board[0].size();
        if(i<0 || i>=m || j<0|| j>=n || visited[i][j]||board[i][j]=='X')
            return;

        visited[i][j]=true;
        dfs(board, i-1, j, visited);
        dfs(board, i+1, j, visited);
        dfs(board, i, j-1, visited);
        dfs(board, i, j+1, visited);
    }


    void solve(vector<vector<char>>& board) {
        int m=board.size();
        int n=board[0].size();
        vector<vector<bool>>   visited(m, vector<bool>(n, false));
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if((i==0 || i==m-1 || j==0 || j==n-1) &&  board[i][j]=='O'){
                    dfs(board, i, j, visited);
                }
            }
        }

        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';
            }
        }
    }
};
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        p = {}
        def find(x):
            p.setdefault(x, x)
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]
        def union(x, y):
            p[find(y)] = find(x)
        if not board or not board[0]: return
        R = len(board)
        C = len(board[0])
        dummy = R * C
        for i in range(R):
            for j in range(C):
                if board[i][j] == "O":
                    if not i or i == R - 1 or not j or j == C - 1:
                        union(i * C + j, dummy)
                    else:
                        for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                            if board[i + x][j + y] == "O":
                                union(i * C + j, (i + x) * C + (j + y))
        for i in range(R):
            for j in range(C):
                if find(dummy) != find(i * C + j):
                    board[i][j] = "X"