题目描述

给定一个二维地图，仅包含'X'和'O'(字母O)，请攻占所有被'X'包围的'O'。
一片区域被攻占，则将这片区域的'O'变成'X'。

样例

输入：

X X X X
X O O X
X X O X
X O X X

输出：

X X X X
X X X X
X X X X
X O X X

解释：边界上的'O'不算被包围，所有不在边界上且不与边界相连的'O'都会被攻占。此题中的相邻指上下左右四个位置相邻。

算法

(Flood Fill, 深度优先遍历) $O(n^2)$

逆向考虑问题，我们先统计出哪些区域不会被攻占，然后将其它区域都变成'X'即可。

具体做法如下：

1. 开一个二维布尔数组，记录哪些区域被遍历过。
2. 枚举所有边界上的'O'，从该位置做Flood Fill，即做深度优先遍历，只遍历是'O'的位置，并将所有遍历到的位置都标记成true。
3. 将所有未遍历到的位置变成'X'。

时间复杂度分析：每个位置仅被遍历一次，所以时间复杂度是 $O(n^2)$，其中 $n$ 是地图的边长。

C++ 代码

class Solution {
public:
    vector<vector<bool>> st;
    int n, m;

    void solve(vector<vector<char>>& board) {
        if (board.empty()) return;
        n = board.size(), m = board[0].size();
        for (int i = 0; i < n; i ++ )
        {
            vector<bool> temp;
            for (int j = 0; j < m; j ++ )
                temp.push_back(false);
            st.push_back(temp);
        }

        for (int i = 0; i < n; i ++ )
        {
            if (board[i][0] == 'O') dfs(i, 0, board);
            if (board[i][m - 1] == 'O') dfs(i, m - 1, board);
        }
        for (int i = 0; i < m; i ++ )
        {
            if (board[0][i] == 'O') dfs(0, i, board);
            if (board[n - 1][i] == 'O') dfs(n - 1, i, board);
        }

        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (!st[i][j])
                    board[i][j] = 'X';
    }

    void dfs(int x, int y, vector<vector<char>>&board)
    {
        st[x][y] = true;
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        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 && !st[a][b] && board[a][b] == 'O')
                dfs(a, b, board);
        }
    }
};