题目链接：130. 被围绕的区域

题解：

经典的逆向思维算法，Flood Fill

题目简述：

给定一个二维矩阵只包含O和X，找到没有被包围的O用X填充。

题解：

题目理解：

  • 任何与边界的O相连的O都会被填充为X
  • 任何与不与边界的O相连的O都不会被填充为X

逆向思维Flood Fill：

  • 我们先将与边界上的O相连的O全部标记出来，即换一个字符例如#
  • 此时除了X和#剩下的O就是需要被修改为X的了
  • 只需一遍扫描即可，将O换为X，将#换为O

注意：vector为空的特判！

时间复杂度：每个点最多遍历两次，为O(n^2)

AC代码：

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
31
32
33
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;
        if(board.empty() || board[0].empty()) return;
        n = board.size(), m = board[0].size();
        for(int i = 0; i < n; i++){
            if(board[i][0] == 'O') dfs(i, 0);
            if(board[i][m - 1] == 'O') dfs(i, m - 1);
        }
        for(int i = 0; i < m; i++){
            if(board[0][i] == 'O') dfs(0, i);
            if(board[n - 1][i] == 'O') 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 if(board[i][j] == 'O') 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);
        }
    }
};