Flood Fill

首先我们能确定四周的O一定不会变成X，所以我们从四周所有的O开始遍历连通块，最终没被遍历过并且是O的点一定是被围绕的，则将这些O变为X

1.第一行和最后一行所有O遍历连通块

2.第一列和最后一列所有O遍历连通块

3.最终图中没被遍历过的O变为X

可以用dfs，也可以bfs

$ 时间复杂度O(NM) $

注意：细节多..特别是遍历四周的点O时候，N和M

参考文献

lc究极班

AC代码

class Solution {
public:
    vector<vector<bool>> st;
    int n, m;
    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

    void dfs(vector<vector<char>>& g, int x ,int y){
        st[x][y] = true;
        //上下四个点遍历
        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) continue;
            if (g[a][b] == 'X' || st[a][b]) continue;//遍历过/非O
            dfs(g, a, b);
        }
    }

    void solve(vector<vector<char>>& g) {
        if (g.empty() || g[0].empty()) return ; 
        n = g.size(), m = g[0].size();
        st = vector<vector<bool>> (n, vector<bool>(m , false));

        //第一列和最后一列
        for (int i = 0 ; i < n ; i ++){
            if (g[i][0] == 'O' && st[i][0] == false)
                dfs(g, i, 0);
            if (g[i][m - 1] == 'O' && st[i][m - 1] == false){
                dfs(g, i, m - 1);
            }
        }
        //第一行和最后一行
        for (int i = 0 ; i < m ; i ++){
            if (g[0][i] == 'O' && st[0][i] == false)
                dfs(g, 0, i);
            if (g[n - 1][i] == 'O' && st[n - 1][i] == false){
                dfs(g, n - 1, i);
            }
        }

        //所有没遍历过的0变为x
        for (int i = 1 ; i < n - 1 ; i ++){
            for (int j = 1 ; j < m - 1 ; j ++){
                if (g[i][j] == 'O' && st[i][j] == false)
                    g[i][j] = 'X';
            }
        }

    }
};