被围绕的区域

被围绕的区域

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

示例 1：

输入：board = [["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' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
示例 2：

输入：board = [["X"]]
输出：[["X"]]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 'X' 或 'O'

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/surrounded-regions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

如果一个区域没有被围住那么一定可以到达边界，在使用BFS将区域连成一块的过程中顺便判断这个区域是否被围起来即可。在BFS过程中需要记录遍历过的节点，以便区域被包围时能够修改。

code

class Solution {
public:

    //不被包围的O:必然能越界
    //BFS将O连接起来的时候顺便判断是不是被围住了
    //BFS 还要记录之前遍历过的节点
    
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};
    

    void solve(vector<vector<char>>& board) {
        
        int m = board.size(),n = board[0].size();

        int p[m * n];
        for(int i = 0;i < m * n;i ++) p[i] = i;

        vector<vector<int>> visit(m,vector<int>(n,0));
        queue<pair<int,int>> path;

        for(int i = 0;i < m;i ++)
        {
            for(int j = 0;j < n;j ++)
            {
                if(!visit[i][j] && board[i][j] == 'O')
                {
                    bool surrounded = true;
                    queue<pair<int,int>> q;
                    q.push({i,j});
                    path.push({i,j});
                    visit[i][j] = 1;

                    while(!q.empty())
                    {
                        pair<int,int> cur = q.front();
                        q.pop();

                        for(int k = 0;k < 4;k ++)
                        {
                            int x = cur.first + dx[k];
                            int y = cur.second + dy[k];
                            if(x < 0 || x >= m || y < 0 || y >= n) surrounded = false;
                            if(x >= 0 && x < m && y >= 0 && y < n && !visit[x][y] && board[x][y] == 'O')
                            {
                                q.push({x,y});
                                path.push({x,y});
                                visit[x][y] = 1;
                            }
                        }
                    }

                    if(surrounded) while(!path.empty()) board[path.front().first][path.front().second] = 'X',path.pop();
                    else while(!path.empty()) path.pop();
                }        
            }
        }
        
    }
};