图：Flood Fill

睡不醒的鲤鱼 2022-05-16 每日一题 LeetCode

# 0130. 被围绕的区域 (opens new window)

题目

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

解析

从四周向中间 DFS，将所有与最外层 O 相连通的区域标记，最后将剩余的 O 更改为 X。

代码

class Solution {
    int m, n;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
public:
    void solve(vector<vector<char>>& board) {
        m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][n - 1] == 'O') dfs(board, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') dfs(board, 0, j);
            if (board[m - 1][j] == 'O') dfs(board, m - 1, j);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '#') board[i][j] = 'O';
                else board[i][j] = 'X';
            }
        }
    }

    void dfs(vector<vector<char>>& board, int x, int y) {
        board[x][y] = '#';
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == 'O') {
                dfs(board, nx, ny);
            }
        }
    }
};