力扣(LeetCode)130. 被围绕的区域(C++)

dfs

只有和边界相连的 $O$ 不会被 $X$ 包围。遍历边界，搜索边界 $O$ 的连通块，标记这些连通块。最后一次遍历矩阵，将标记的格子改回 $O$ ，其他格子改成 $X$ ，即为所求。

提示 : 可以用数组标记连通块，也可以将连通块的字符改成没有出现过的助记符，在遍历时，将标记的格子，或者助记符改回 $O$ 即可。
提示 : $dx/dy$ 是方向数组，便于搜索操作。

class Solution {
public:
    vector<vector<char>> board;
    int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
    int n ,m;
    void solve(vector<vector<char>>& _board) {
        board = _board;
        n = board.size(),m = board[0].size();
        for(int i = 0;i<n;i++) {
            if('O'==board[i][0]) dfs(i,0);
            if('O'==board[i][m-1]) dfs(i,m-1);
        }
        for(int i = 0;i<m;i++){
            if('O'==board[0][i]) dfs(0,i);
            if('O'==board[n-1][i]) dfs(n-1,i);
        }
        for(int i = 0;i<n;i++)
            for(int j = 0;j<m;j++)
                if('#'==board[i][j]) board[i][j] = 'O';
                else board[i][j] = 'X';
        _board = board;
    }
    void dfs(int x,int y){
        board[x][y] = '#';
        for(int i = 0;i<4;i++){
            int a = x + dx[i], b = y + dy[i];
            if(a>=0&&a<n&&b>=0&&b<m&&board[a][b]=='O') dfs(a,b);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

1. 时间复杂度 : $O(n\times m)$ ， $n$ 是矩阵的行， $m$ 是矩阵的列， 对矩阵边界尝试深搜的最坏时间复杂度 $O(n\times m)$ ，一次遍历矩阵的时间复杂度 $O(n\times m)$ ，忽略常数时间复杂度 $O(n\times m)$。
2. 空间复杂度 : $O(n\times m)$ ， 深搜压栈最大深度等于矩阵大小 $O(n\times m)$ 。

AC