1 题目：被围绕的区域
官方标定难度：中
给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ 组成，捕获 所有 被围绕的区域：
连接：一个单元格与水平或垂直方向上相邻的单元格连接。
区域：连接所有 ‘O’ 的单元格来形成一个区域。
围绕：如果您可以用 ‘X’ 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 ‘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”]]
解释：
在上图中，底部的区域没有被捕获，因为它在 board 的边缘并且不能被围绕。
示例 2：
输入：board = [[“X”]]
输出：[[“X”]]
提示：
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 ‘X’ 或 ‘O’
2 solution
先把四周没有被围住的部分标记一下，然后将剩下的部分修改过来即可
代码
class Solution {
public:
void solve(int *dr, int *dc, int r, int c, vector<vector<char>> &board) {board[r][c] = 'Y';for (int i = 0; i < 4; i++) {int rr = dr[i] + r;int cc = dc[i] + c;if(rr >= 0 && rr < board.size() && cc >= 0 && cc < board[0].size() && board[rr][cc] == 'O'){solve(dr, dc, rr, cc, board);}}
}void solve(vector<vector<char>> &board) {int dr[] = {0, 1, -1, 0};int dc[] = {1, 0, 0, -1};for(int i = 0; i < board.size(); i++){if(board[i][0] == 'O') solve(dr, dc, i, 0, board);if(board[i][board[0].size() - 1] == 'O') solve(dr, dc, i, board[0].size() - 1, board);}for(int j = 0; j < board[0].size(); j++){if(board[0][j] == 'O') solve(dr, dc, 0, j, board);if(board[board.size() - 1][j] == 'O') solve(dr, dc, board.size() - 1, j, board);}for (auto &row: board) {for (auto &c: row) {if (c == 'Y') c = 'O';else if (c == 'O') c = 'X';}}
}};
结果
