题目描述

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 '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' 都不会被填充为 'X'。

任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。

如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

算法1

本题目使用BFS 找出与边连接的’O’，那么剩下的’O’就是需要填写为’X’的。
考虑到邻接特性 所以使用并查集也是可以的

C++ 代码

class Solution {
public:

int addx[4] = { 1,-1,0,0 };
int addy[4] = { 0,0,-1,1 };


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

    queue<pair<int, int>> q;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if ( (i == 0 || j == 0 || i == n - 1 || j == m-1 ) &&  board[i][j] == 'O') {
                //只要是边上的 O 就放入BFS搜索队列
                board[i][j] = 'T';
                q.push({ i,j });
            }
        }
    }

    while (q.size()) {
        int x = q.front().first; 
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int newx = x + addx[i];
            int newy = y + addy[i];

            if (newx >= 0 && newx < n && newy >= 0 && newy < m && board[newx][newy] == 'O') {
                board[newx][newy] = 'T';
                q.push({ newx,newy });
            }
        }
    }

    //遍历完成后 所有与边相邻的O 变成了T
    //我需要全部填充X 然后将T变成O 即可
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 'T') {
                board[i][j] = 'O'; 
            }
            else if (board[i][j] != 'X') {
                board[i][j] = 'X';
            }
        }
    }

    return;
}

};