参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
- 输入：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'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
这道题目和1020. 飞地的数量正好反过来了，1020. 飞地的数量是求 地图中间的空格数，而本题是要把地图中间的'O'都改成'X'。
那么两题在思路上也是差不多的。
依然是从地图周边出发，将周边空格相邻的'O'都做上标记，然后在遍历一遍地图，遇到 'O' 且没做过标记的，那么都是地图中间的'O'，全部改成'X'就行。
有的录友可能想，我在定义一个 visited 二维数组，单独标记周边的'O'，然后遍历地图的时候同时对 数组board 和 数组visited 进行判断，是否'O'改成'X'。
这样做其实就有点麻烦了，不用额外定义空间了，标记周边的'O'，可以直接改board的数值为其他特殊值。
步骤一：深搜或者广搜将地图周边的'O'全部改成'A'，如图所示：
步骤二：在遍历地图，将'O'全部改成'X'（地图中间的'O'改成了'X'），将'A'改回'O'（保留的地图周边的'O'），如图所示：
整体C++代码如下，以下使用dfs实现，其实遍历方式dfs，bfs都是可以的。
class Solution {
private:
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
void dfs(vector<vector<char>>& board, int x, int y) {
board[x][y] = 'A';
for (int i = 0; i < 4; i++) { // 向四个方向遍历
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
// 超过边界
if (nextx < 0 || nextx >= board.size() || nexty < 0 || nexty >= board[0].size()) continue;
// 不符合条件，不继续遍历
if (board[nextx][nexty] == 'X' || board[nextx][nexty] == 'A') continue;
dfs (board, nextx, nexty);
}
return;
}
public:
void solve(vector<vector<char>>& board) {
int n = board.size(), m = board[0].size();
// 步骤一：
// 从左侧边，和右侧边 向中间遍历
for (int i = 0; i < n; i++) {
if (board[i][0] == 'O') dfs(board, i, 0);
if (board[i][m - 1] == 'O') dfs(board, i, m - 1);
}
// 从上边和下边 向中间遍历
for (int j = 0; j < m; j++) {
if (board[0][j] == 'O') dfs(board, 0, j);
if (board[n - 1][j] == 'O') dfs(board, n - 1, j);
}
// 步骤二：
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == 'A') board[i][j] = 'O';
}
}
}
};// 广度优先遍历
// 使用 visited 数组进行标记
class Solution {
private static final int[][] position = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 四个方向
public void solve(char[][] board) {
// rowSize：行的长度，colSize：列的长度
int rowSize = board.length, colSize = board[0].length;
boolean[][] visited = new boolean[rowSize][colSize];
Queue<int[]> queue = new ArrayDeque<>();
// 从左侧边，和右侧边遍历
for (int row = 0; row < rowSize; row++) {
if (board[row][0] == 'O') {
visited[row][0] = true;
queue.add(new int[]{row, 0});
}
if (board[row][colSize - 1] == 'O') {
visited[row][colSize - 1] = true;
queue.add(new int[]{row, colSize - 1});
}
}
// 从上边和下边遍历，在对左侧边和右侧边遍历时我们已经遍历了矩阵的四个角
// 所以在遍历上边和下边时可以不用遍历四个角
for (int col = 1; col < colSize - 1; col++) {
if (board[0][col] == 'O') {
visited[0][col] = true;
queue.add(new int[]{0, col});
}
if (board[rowSize - 1][col] == 'O') {
visited[rowSize - 1][col] = true;
queue.add(new int[]{rowSize - 1, col});
}
}
// 广度优先遍历，把没有被 'X' 包围的 'O' 进行标记
while (!queue.isEmpty()) {
int[] current = queue.poll();
for (int[] pos: position) {
int row = current[0] + pos[0], col = current[1] + pos[1];
// 如果范围越界、位置已被访问过、该位置的值不是 'O'，就直接跳过
if (row < 0 || row >= rowSize || col < 0 || col >= colSize) continue;
if (visited[row][col] || board[row][col] != 'O') continue;
visited[row][col] = true;
queue.add(new int[]{row, col});
}
}
// 遍历数组，把没有被标记的 'O' 修改成 'X'
for (int row = 0; row < rowSize; row++) {
for (int col = 0; col < colSize; col++) {
if (board[row][col] == 'O' && !visited[row][col]) board[row][col] = 'X';
}
}
}
}// 广度优先遍历
// 直接修改 board 的值为其他特殊值
class Solution {
private static final int[][] position = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 四个方向
public void solve(char[][] board) {
// rowSize：行的长度，colSize：列的长度
int rowSize = board.length, colSize = board[0].length;
Queue<int[]> queue = new ArrayDeque<>();
// 从左侧边，和右侧边遍历
for (int row = 0; row < rowSize; row++) {
if (board[row][0] == 'O')
queue.add(new int[]{row, 0});
if (board[row][colSize - 1] == 'O')
queue.add(new int[]{row, colSize - 1});
}
// 从上边和下边遍历，在对左侧边和右侧边遍历时我们已经遍历了矩阵的四个角
// 所以在遍历上边和下边时可以不用遍历四个角
for (int col = 1; col < colSize - 1; col++) {
if (board[0][col] == 'O')
queue.add(new int[]{0, col});
if (board[rowSize - 1][col] == 'O')
queue.add(new int[]{rowSize - 1, col});
}
// 广度优先遍历，把没有被 'X' 包围的 'O' 修改成特殊值
while (!queue.isEmpty()) {
int[] current = queue.poll();
board[current[0]][current[1]] = 'A';
for (int[] pos: position) {
int row = current[0] + pos[0], col = current[1] + pos[1];
// 如果范围越界、该位置的值不是 'O'，就直接跳过
if (row < 0 || row >= rowSize || col < 0 || col >= colSize) continue;
if (board[row][col] != 'O') continue;
queue.add(new int[]{row, col});
}
}
// 遍历数组，把 'O' 修改成 'X'，特殊值修改成 'O'
for (int row = 0; row < rowSize; row++) {
for (int col = 0; col < colSize; col++) {
if (board[row][col] == 'A') board[row][col] = 'O';
else if (board[row][col] == 'O') board[row][col] = 'X';
}
}
}
}//BFS（使用helper function）
class Solution {
int[][] dir ={{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public void solve(char[][] board) {
for(int i = 0; i < board.length; i++){
if(board[i][0] == 'O') bfs(board, i, 0);
if(board[i][board[0].length - 1] == 'O') bfs(board, i, board[0].length - 1);
}
for(int j = 1 ; j < board[0].length - 1; j++){
if(board[0][j] == 'O') bfs(board, 0, j);
if(board[board.length - 1][j] == 'O') bfs(board, board.length - 1, j);
}
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(board[i][j] == 'O') board[i][j] = 'X';
if(board[i][j] == 'A') board[i][j] = 'O';
}
}
}
private void bfs(char[][] board, int x, int y){
Queue<Integer> que = new LinkedList<>();
board[x][y] = 'A';
que.offer(x);
que.offer(y);
while(!que.isEmpty()){
int currX = que.poll();
int currY = que.poll();
for(int i = 0; i < 4; i++){
int nextX = currX + dir[i][0];
int nextY = currY + dir[i][1];
if(nextX < 0 || nextY < 0 || nextX >= board.length || nextY >= board[0].length)
continue;
if(board[nextX][nextY] == 'X'|| board[nextX][nextY] == 'A')
continue;
bfs(board, nextX, nextY);
}
}
}
}// 深度优先遍历
// 使用 visited 数组进行标记
class Solution {
private static final int[][] position = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 四个方向
public void dfs(char[][] board, int row, int col, boolean[][] visited) {
for (int[] pos: position) {
int nextRow = row + pos[0], nextCol = col + pos[1];
// 位置越界
if (nextRow < 0 || nextRow >= board.length || nextCol < 0 || nextCol >= board[0].length)
continue;
// 位置已被访问过、新位置值不是 'O'
if (visited[nextRow][nextCol] || board[nextRow][nextCol] != 'O') continue;
visited[nextRow][nextCol] = true;
dfs(board, nextRow, nextCol, visited);
}
}
public void solve(char[][] board) {
int rowSize = board.length, colSize = board[0].length;
boolean[][] visited = new boolean[rowSize][colSize];
// 从左侧遍、右侧遍遍历
for (int row = 0; row < rowSize; row++) {
if (board[row][0] == 'O' && !visited[row][0]) {
visited[row][0] = true;
dfs(board, row, 0, visited);
}
if (board[row][colSize - 1] == 'O' && !visited[row][colSize - 1]) {
visited[row][colSize - 1] = true;
dfs(board, row, colSize - 1, visited);
}
}
// 从上边和下边遍历，在对左侧边和右侧边遍历时我们已经遍历了矩阵的四个角
// 所以在遍历上边和下边时可以不用遍历四个角
for (int col = 1; col < colSize - 1; col++) {
if (board[0][col] == 'O' && !visited[0][col]) {
visited[0][col] = true;
dfs(board, 0, col, visited);
}
if (board[rowSize - 1][col] == 'O' && !visited[rowSize - 1][col]) {
visited[rowSize - 1][col] = true;
dfs(board, rowSize - 1, col, visited);
}
}
// 遍历数组，把没有被标记的 'O' 修改成 'X'
for (int row = 0; row < rowSize; row++) {
for (int col = 0; col < colSize; col++) {
if (board[row][col] == 'O' && !visited[row][col]) board[row][col] = 'X';
}
}
}
}// 深度优先遍历
// // 直接修改 board 的值为其他特殊值
class Solution {
private static final int[][] position = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 四个方向
public void dfs(char[][] board, int row, int col) {
for (int[] pos: position) {
int nextRow = row + pos[0], nextCol = col + pos[1];
// 位置越界
if (nextRow < 0 || nextRow >= board.length || nextCol < 0 || nextCol >= board[0].length)
continue;
// 新位置值不是 'O'
if (board[nextRow][nextCol] != 'O') continue;
board[nextRow][nextCol] = 'A'; // 修改为特殊值
dfs(board, nextRow, nextCol);
}
}
public void solve(char[][] board) {
int rowSize = board.length, colSize = board[0].length;
// 从左侧遍、右侧遍遍历
for (int row = 0; row < rowSize; row++) {
if (board[row][0] == 'O') {
board[row][0] = 'A';
dfs(board, row, 0);
}
if (board[row][colSize - 1] == 'O') {
board[row][colSize - 1] = 'A';
dfs(board, row, colSize - 1);
}
}
// 从上边和下边遍历，在对左侧边和右侧边遍历时我们已经遍历了矩阵的四个角
// 所以在遍历上边和下边时可以不用遍历四个角
for (int col = 1; col < colSize - 1; col++) {
if (board[0][col] == 'O') {
board[0][col] = 'A';
dfs(board, 0, col);
}
if (board[rowSize - 1][col] == 'O') {
board[rowSize - 1][col] = 'A';
dfs(board, rowSize - 1, col);
}
}
// 遍历数组，把 'O' 修改成 'X'，特殊值修改成 'O'
for (int row = 0; row < rowSize; row++) {
for (int col = 0; col < colSize; col++) {
if (board[row][col] == 'O') board[row][col] = 'X';
else if (board[row][col] == 'A') board[row][col] = 'O';
}
}
}
}//DFS(有終止條件)
class Solution {
int[][] dir ={{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public void solve(char[][] board) {
for(int i = 0; i < board.length; i++){
if(board[i][0] == 'O') dfs(board, i, 0);
if(board[i][board[0].length - 1] == 'O') dfs(board, i, board[0].length - 1);
}
for(int j = 1 ; j < board[0].length - 1; j++){
if(board[0][j] == 'O') dfs(board, 0, j);
if(board[board.length - 1][j] == 'O') dfs(board, board.length - 1, j);
}
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(board[i][j] == 'O') board[i][j] = 'X';
if(board[i][j] == 'A') board[i][j] = 'O';
}
}
}
private void dfs(char[][] board, int x, int y){
if(board[x][y] == 'X'|| board[x][y] == 'A')
return;
board[x][y] = 'A';
for(int i = 0; i < 4; i++){
int nextX = x + dir[i][0];
int nextY = y + dir[i][1];
if(nextX < 0 || nextY < 0 || nextX >= board.length || nextY >= board[0].length)
continue;
// if(board[nextX][nextY] == 'X'|| board[nextX][nextY] == 'A')
// continue;
dfs(board, nextX, nextY);
}
}
}// 深度优先遍历
class Solution:
dir_list = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
row_size = len(board)
column_size = len(board[0])
visited = [[False] * column_size for _ in range(row_size)]
# 从边缘开始，将边缘相连的O改成A。然后遍历所有，将A改成O，O改成X
# 第一行和最后一行
for i in range(column_size):
if board[0][i] == "O" and not visited[0][i]:
self.dfs(board, 0, i, visited)
if board[row_size-1][i] == "O" and not visited[row_size-1][i]:
self.dfs(board, row_size-1, i, visited)
# 第一列和最后一列
for i in range(1, row_size-1):
if board[i][0] == "O" and not visited[i][0]:
self.dfs(board, i, 0, visited)
if board[i][column_size-1] == "O" and not visited[i][column_size-1]:
self.dfs(board, i, column_size-1, visited)
for i in range(row_size):
for j in range(column_size):
if board[i][j] == "A":
board[i][j] = "O"
elif board[i][j] == "O":
board[i][j] = "X"
def dfs(self, board, x, y, visited):
if visited[x][y] or board[x][y] == "X":
return
visited[x][y] = True
board[x][y] = "A"
for i in range(4):
new_x = x + self.dir_list[i][0]
new_y = y + self.dir_list[i][1]
if new_x >= len(board) or new_y >= len(board[0]) or new_x < 0 or new_y < 0:
continue
self.dfs(board, new_x, new_y, visited)
