# 被围绕的区域
给你一个 <code>m x n</code> 的矩阵 <code>board</code> ，由若干字符 <code>'X'</code> 和 <code>'O'</code> ，找到所有被 <code>'X'</code> 围绕的区域，并将这些区域里所有的 <code>'O'</code> 用 <code>'X'</code> 填充。
<div class="original__bRMd">
<div>
<p> </p>

<p><strong>示例 1：</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/19/xogrid.jpg" style="width: 550px; height: 237px;" />
<pre>
<strong>输入：</strong>board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
<strong>输出：</strong>[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
<strong>解释：</strong>被围绕的区间不会存在于边界上，换句话说，任何边界上的 <code>'O'</code> 都不会被填充为 <code>'X'</code>。 任何不在边界上，或不与边界上的 <code>'O'</code> 相连的 <code>'O'</code> 最终都会被填充为 <code>'X'</code>。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
</pre>

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong>board = [["X"]]
<strong>输出：</strong>[["X"]]
</pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>m == board.length</code></li>
	<li><code>n == board[i].length</code></li>
	<li><code>1 <= m, n <= 200</code></li>
	<li><code>board[i][j]</code> 为 <code>'X'</code> 或 <code>'O'</code></li>
</ul>
</div>
</div>

<p>以下错误的选项是？</p>

## aop
### before
```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after
```cpp
int main()
{
    Solution sol;
    vector<vector<char>> board = {{'X', 'X', 'X', 'X'}, {'X', 'O', 'O', 'X'}, {'X', 'X', 'O', 'X'}, {'X', 'O', 'X', 'X'}};

    sol.solve(board);
    for (auto i : board)
    {
        for (auto j : i)
            cout << j << " ";
        cout << endl;
    }
    return 0;
}
```

## 答案
```cpp
class Solution
{
public:
    vector<vector<bool>> st;
    int m, n;
    void bfs(vector<vector<char>> &board, int a, int b)
    {
        int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
        st[a][b] = true;
        queue<pair<int, int>> q;
        q.push(make_pair(a, b));
        while (q.size())
        {
            pair<int, int> t = q.front();
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int x = dx[i] + t.first, y = dy[i] + t.second;
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O' && !st[x][y])
                {
                    q.push(make_pair(x, y));
                    st[x][y] = true;
                }
            }
        }
    }
    void solve(vector<vector<char>> &board)
    {
        if (!board.size())
            return;
        m = board.size(), n = board[0].size();
        st = vector<vector<bool>>(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++)
        {
            if (board[i][0] == 'O')
                bfs(board, i, 0);
            if (board[i][n] == 'O')
                bfs(board, i, n - 1);
        }
        for (int i = 0; i < n; i++)
        {
            if (board[0][i] == 'O')
                bfs(board, 0, i);
            if (board[m][i] == 'O')
                bfs(board, m - 1, i);
        }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (!st[i][j])
                    board[i][j] = 'X';
    }
};
```
## 选项

### A
```cpp
class Solution
{
public:
    int n, m;

    void dfs(vector<vector<char>> &board, int x, int y)
    {
        if (x < 0 || y < 0 || x >= m || y >= n || board[x][y] != 'O')
            return;
        board[x][y] = 'A';
        dfs(board, x + 1, y);
        dfs(board, x, y + 1);
        dfs(board, x - 1, y);
        dfs(board, x, y - 1);
    }
    void solve(vector<vector<char>> &board)
    {

        m = board.size();

        if (m == 0)
            return;

        n = board[0].size();

        for (int i = 0; i < m; i++)
        {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }

        for (int i = 1; i < n - 1; i++)
        {
            dfs(board, 0, i);
            dfs(board, m - 1, i);
        }

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (board[i][j] == 'A')
                    board[i][j] = 'O';
                else if (board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }
};
```

### B
```cpp
class Solution
{
public:
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    queue<pair<int, int>> s;
    void solve(vector<vector<char>> &board)
    {
        int n = board.size();
        if (n <= 2)
            return;
        int m = board[0].size();
        if (m <= 2)
            return;

        for (int i = 0; i < m; i++)
        {
            if (board[0][i] == 'O')
                s.push({0, i});
            if (board[n - 1][i] == 'O')
                s.push({n - 1, i});
        }
        for (int i = 1; i < n - 1; i++)
        {
            if (board[i][0] == 'O')
                s.push({i, 0});
            if (board[i][m - 1] == 'O')
                s.push({i, m - 1});
        }
        while (!s.empty())
        {
            int x = s.front().first, y = s.front().second;
            board[x][y] = '#';
            s.pop();
            for (int i = 0; i < 4; i++)
            {
                int mx = x + dx[i], my = y + dy[i];
                if (mx < 0 || my < 0 || mx >= n || my >= m || board[mx][my] != 'O')
                {
                    continue;
                }
                s.push({mx, my});
            }
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (board[i][j] == '#')
                    board[i][j] = 'O';
                else if (board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }
};

```

### C
```cpp
class Solution
{
public:
    void dfs(vector<vector<char>> &board, int row, int col)
    {
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size())
            return;
        if (board[row][col] != 'O')
            return;
        board[row][col] = '+';
        dfs(board, row + 1, col);
        dfs(board, row, col + 1);
        dfs(board, row - 1, col);
        dfs(board, row, col - 1);
    }

    void solve(vector<vector<char>> &board)
    {
        if (board.size() <= 1 || board[0].size() <= 2)
            return;
        for (int i = 0; i < board.size(); i++)
        {
            if (board[i][0] == 'O')
                dfs(board, i, 0);
            if (board[i][board[0].size() - 1] == 'O')
                dfs(board, i, board[0].size() - 1);
        }
        for (int i = 0; i < board[0].size(); i++)
        {
            if (board[0][i] == 'O')
                dfs(board, 0, i);
            if (board[board.size() - 1][i] == 'O')
                dfs(board, board.size() - 1, i);
        }

        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                if (board[i][j] == '+')
                    board[i][j] = 'O';
                else if (board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }
};
```