参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！

# 130. 被围绕的区域

题目链接 (opens new window)

给你一个 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. 飞地的数量 (opens new window)是求地图中间的空格数，而本题是要把地图中间的'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';
            }
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

# 其他语言版本

# Java

// 广度优先遍历
// 使用 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';
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

// 广度优先遍历
// 直接修改 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'; 
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

//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);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

// 深度优先遍历
// 使用 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';
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

// 深度优先遍历
// // 直接修改 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';
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

//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);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# Python3

// 深度优先遍历
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# JavaScript

/**
 * @description 深度搜索优先
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
function solve(board) {
  const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  const [rowSize, colSize] = [board.length, board[0].length];

  function dfs(board, x, y) {
    board[x][y] = 'A';
    for (let i = 0; i < 4; i++) {
      const nextX = dir[i][0] + x;
      const nextY = dir[i][1] + y;
      if (nextX < 0 || nextX >= rowSize || nextY < 0 || nextY >= colSize) {
        continue;
      }
      if (board[nextX][nextY] === 'O') {
        dfs(board, nextX, nextY);
      }
    }
  }

  for (let i = 0; i < rowSize; i++) {
    if (board[i][0] === 'O') {
      dfs(board, i, 0);
    }
    if (board[i][colSize - 1] === 'O') {
      dfs(board, i, colSize - 1);
    }
  }

  for (let i = 1; i < colSize - 1; i++) {
    if (board[0][i] === 'O') {
      dfs(board, 0, i);
    }
    if (board[rowSize - 1][i] === 'O') {
      dfs(board, rowSize - 1, i);
    }
  }

  for (let i = 0; i < rowSize; i++) {
    for (let k = 0; k < colSize; k++) {
      if (board[i][k] === 'A') {
        board[i][k] = 'O';
      } else if (board[i][k] === 'O') {
        board[i][k] = 'X';
      }
    }
  }
}

/**
 * @description 广度搜索优先
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
function solve(board) {
  const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  const [rowSize, colSize] = [board.length, board[0].length];

  function bfs(board, x, y) {
    board[x][y] = 'A';
    const stack = [y, x];

    while (stack.length !== 0) {
      const top = [stack.pop(), stack.pop()];
      for (let i = 0; i < 4; i++) {
        const nextX = dir[i][0] + top[0];
        const nextY = dir[i][1] + top[1];

        if (nextX < 0 || nextX >= rowSize || nextY < 0 || nextY >= colSize) {
          continue;
        }

        if (board[nextX][nextY] === 'O') {
          board[nextX][nextY] = 'A';
          stack.push(nextY, nextX);
        }
      }
    }

    for (let i = 0; i < 4; i++) {
      const nextX = dir[i][0] + x;
      const nextY = dir[i][1] + y;
      if (nextX < 0 || nextX >= rowSize || nextY < 0 || nextY >= colSize) {
        continue;
      }
      if (board[nextX][nextY] === 'O') {
        dfs(board, nextX, nextY);
      }
    }
  }

  for (let i = 0; i < rowSize; i++) {
    if (board[i][0] === 'O') {
      bfs(board, i, 0);
    }
    if (board[i][colSize - 1] === 'O') {
      bfs(board, i, colSize - 1);
    }
  }

  for (let i = 1; i < colSize - 1; i++) {
    if (board[0][i] === 'O') {
      bfs(board, 0, i);
    }
    if (board[rowSize - 1][i] === 'O') {
      bfs(board, rowSize - 1, i);
    }
  }

  for (let i = 0; i < rowSize; i++) {
    for (let k = 0; k < colSize; k++) {
      if (board[i][k] === 'A') {
        board[i][k] = 'O';
      } else if (board[i][k] === 'O') {
        board[i][k] = 'X';
      }
    }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

# Go

dfs:

var DIRECTIONS = [4][2]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}

func solve(board [][]byte) {
	rows, cols := len(board), len(board[0])
	// 列
	for i := 0; i < rows; i++ {
		if board[i][0] == 'O' {
			dfs(board, i, 0)
		}
		if board[i][cols-1] == 'O' {
			dfs(board, i, cols-1)
		}
	}
	// 行
	for j := 0; j < cols; j++ {
		if board[0][j] == 'O' {
			dfs(board, 0, j)
		}
		if board[rows-1][j] == 'O' {
			dfs(board, rows-1, j)
		}
	}

	for _, r := range board {
		for j, c := range r {
			if c == 'A' {
				r[j] = 'O'
				continue
			}
			if c == 'O' {
				r[j] = 'X'
			}
		}
	}
}

func dfs(board [][]byte, i, j int) {
	board[i][j] = 'A'
	for _, d := range DIRECTIONS {
		x, y := i+d[0], j+d[1]
		if x < 0 || x >= len(board) || y < 0 || y >= len(board[0]) {
			continue
		}
		if board[x][y] == 'O' {
			dfs(board, x, y)
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

bfs:

var DIRECTIONS = [4][2]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}

func solve(board [][]byte) {
	rows, cols := len(board), len(board[0])
	// 列
	for i := 0; i < rows; i++ {
		if board[i][0] == 'O' {
			bfs(board, i, 0)
		}
		if board[i][cols-1] == 'O' {
			bfs(board, i, cols-1)
		}
	}
	// 行
	for j := 0; j < cols; j++ {
		if board[0][j] == 'O' {
			bfs(board, 0, j)
		}
		if board[rows-1][j] == 'O' {
			bfs(board, rows-1, j)
		}
	}

	for _, r := range board {
		for j, c := range r {
			if c == 'A' {
				r[j] = 'O'
                         	continue
			}
			if c == 'O' {
				r[j] = 'X'
			}
		}
	}
}

func bfs(board [][]byte, i, j int) {
	queue := [][]int{{i, j}}
	board[i][j] = 'A'
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		for _, d := range DIRECTIONS {
			x, y := cur[0]+d[0], cur[1]+d[1]
			if x < 0 || x >= len(board) || y < 0 || y >= len(board[0]) {
				continue
			}
			if board[x][y] == 'O' {
				board[x][y] = 'A'
				queue = append(queue, []int{x, y})
			}
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

# Rust

bfs:

impl Solution {
    const DIRECTIONS: [(isize, isize); 4] = [(0, 1), (0, -1), (1, 0), (-1, 0)];
    pub fn solve(board: &mut Vec<Vec<char>>) {
        let (rows, cols) = (board.len(), board[0].len());
        // 列
        for i in 0..rows {
            if board[i][0] == 'O' {
                Self::dfs(board, i, 0);
            }
            if board[i][cols - 1] == 'O' {
                Self::dfs(board, i, cols - 1);
            }
        }
        //行
        for j in 0..cols {
            if board[0][j] == 'O' {
                Self::dfs(board, 0, j);
            }
            if board[rows - 1][j] == 'O' {
                Self::dfs(board, rows - 1, j);
            }
        }

        for v in board.iter_mut() {
            for c in v.iter_mut() {
                if *c == 'A' {
                    *c = 'O';
                    continue;
                }
                if *c == 'O' {
                    *c = 'X';
                }
            }
        }
    }

    pub fn dfs(board: &mut [Vec<char>], i: usize, j: usize) {
        board[i][j] = 'A';
        for (d1, d2) in Self::DIRECTIONS {
            let (x, y) = (i as isize + d1, j as isize + d2);
            if x < 0 || x >= board.len() as isize || y < 0 || y >= board[0].len() as isize {
                continue;
            }
            let (x, y) = (x as usize, y as usize);
            if board[x][y] == 'O' {
                Self::dfs(board, x, y);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

bfs:

use std::collections::VecDeque;
impl Solution {
    const DIRECTIONS: [(isize, isize); 4] = [(0, 1), (0, -1), (1, 0), (-1, 0)];
    pub fn solve(board: &mut Vec<Vec<char>>) {
        let (rows, cols) = (board.len(), board[0].len());
        // 列
        for i in 0..rows {
            if board[i][0] == 'O' {
                Self::bfs(board, i, 0);
            }
            if board[i][cols - 1] == 'O' {
                Self::bfs(board, i, cols - 1);
            }
        }
        //行
        for j in 0..cols {
            if board[0][j] == 'O' {
                Self::bfs(board, 0, j);
            }
            if board[rows - 1][j] == 'O' {
                Self::bfs(board, rows - 1, j);
            }
        }

        for v in board.iter_mut() {
            for c in v.iter_mut() {
                if *c == 'A' {
                    *c = 'O';
                    continue;
                }
                if *c == 'O' {
                    *c = 'X';
                }
            }
        }
    }

    pub fn bfs(board: &mut [Vec<char>], i: usize, j: usize) {
        let mut queue = VecDeque::from([(i, j)]);
        board[i][j] = 'A';
        while let Some((i, j)) = queue.pop_front() {
            for (d1, d2) in Self::DIRECTIONS {
                let (x, y) = (i as isize + d1, j as isize + d2);
                if x < 0 || x >= board.len() as isize || y < 0 || y >= board[0].len() as isize {
                    continue;
                }
                let (x, y) = (x as usize, y as usize);
                if board[x][y] == 'O' {
                    board[x][y] = 'A';
                    queue.push_back((x, y));
                }
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55