被围绕的区域

算法流程

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型二维数组 
     * @return char字符型二维数组
     */
    int[] dx = new int[]{-1, 1, 0, 0};
    int[] dy = new int[]{0, 0, -1, 1};
    public char[][] surroundedArea (char[][] board) {
        // 溜边界，先把边界处的O找到，然后锁死它的连通区域
        int n = board.length, m = board[0].length;
        for(int j = 0; j < board[0].length; j++){
            if(board[0][j] == 'O'){
                dfs(board, 0, j);
            }
            if(board[n - 1][j] == 'O'){
                dfs(board, n - 1, j);
            }
        }
        for(int i = 1; i < n - 1; i++){
            if(board[i][0] == 'O'){
                dfs(board, i, 0);
            }
            if(board[i][m - 1] == 'O'){
                dfs(board, i, m - 1);
            }
        }
        // 其他的O就是被围绕的O，将其充填为X
        for(int i = 1; i < n - 1; i++){
            for(int j = 1; j < m - 1; j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
        // 把之前锁死的O改回来
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(board[i][j] == 'L'){
                    board[i][j] = 'O';
                }
            }
        }
        return board;
    }
    
    private void dfs(char[][] board, int x, int y) {
        if(x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != 'O'){
            return;     // 越界或已经不是O就直接返回
        }
        board[x][y] = 'L';    // LOCKED锁住
        for(int i = 0; i < 4; i++){
            dfs(board, x + dx[i], y + dy[i]);
        }
    }
}

import java.util.*;

/**
 * NC226 被围绕的区域
 * @author d3y1
 */
public class Solution {
    private int[] dx = new int[]{0, 1, 0, -1};
    private int[] dy = new int[]{1, 0, -1, 0};
    private int ROW;
    private int COL;
    private boolean[][] isVisited;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 程序入口
     *
     * @param board char字符型二维数组
     * @return char字符型二维数组
     */
    public char[][] surroundedArea (char[][] board) {
        // return solution1(board);
        // return solution11(board);
        // return solution2(board);
        // return solution22(board);
        // return solution3(board);
        return solution4(board);
    }

    /**
     * 模拟法: 直接递归
     * @param board
     * @return
     */
    private char[][] solution1(char[][] board){
        ROW = board.length;
        COL = board[0].length;
        isVisited = new boolean[ROW][COL];

        for(int i=0; i<ROW; i++){
            for(int j=0; j<COL; j++){
                if(board[i][j]=='O' && !isVisited[i][j]){
                    dfs(board, i, j);
                }
            }
        }

        return board;
    }

    /**
     * dfs
     * @param board
     * @param x
     * @param y
     * @return
     */
    private boolean dfs(char[][] board, int x, int y){
        if(board[x][y] == 'X'){
            return true;
        }

        // O -> X
        board[x][y] = 'X';
        isVisited[x][y] = true;

        int nextX, nextY;
        for(int i=0; i<4; i++){
            nextX = x+dx[i];
            nextY = y+dy[i];
            // 不合法 超过边界
            if(!isValid(nextX, nextY)){
                // X -> O
                board[x][y] = 'O';
                return false;
            }
            // 未访问过
            if(!isVisited[nextX][nextY]){
                if(!dfs(board, nextX, nextY)){
                    // X -> O
                    board[x][y] = 'O';
                    return false;
                }
            }
            // 已访问过
            else{
                // 已访问过 但是恢复成O => 说明相邻位置(nextX,nextY)未被围绕, 则当前位置(x,y)也不可能被围绕
                if(board[nextX][nextY] == 'O'){
                    // X -> O
                    board[x][y] = 'O';
                    return false;
                }
            }
        }

        return true;
    }

    /**
     * 模拟法: 直接递归 [简化]
     * @param board
     * @return
     */
    private char[][] solution11(char[][] board){
        ROW = board.length;
        COL = board[0].length;
        isVisited = new boolean[ROW][COL];

        for(int i=0; i<ROW; i++){
            for(int j=0; j<COL; j++){
                check(board, i, j);
            }
        }

        return board;
    }

    /**
     * dfs
     * @param board
     * @param x
     * @param y
     * @return
     */
    private boolean check(char[][] board, int x, int y){
        // 边界为O
        if((x==0||x==ROW-1||y==0||y==COL-1) && board[x][y]=='O'){
            return false;
        }

        if(board[x][y] == 'X'){
            return true;
        }

        if(!isVisited[x][y]){
            board[x][y] = 'X';
            // up
            boolean up = check(board, x-1, y);
            // down
            boolean down = check(board, x+1, y);
            // left
            boolean left = check(board, x, y-1);
            // right
            boolean right = check(board, x, y+1);

            if(up && down && left && right){
                return true;
            }

            board[x][y] = 'O';
            isVisited[x][y] = true;
            return false;
        }

        return false;
    }

    /**
     * 模拟法: 边界递归(由外向内)
     * @param board
     * @return
     */
    private char[][] solution2(char[][] board){
        ROW = board.length;
        COL = board[0].length;

        // 左右边界
        for(int i=0; i<ROW; i++){
            if(board[i][0] == 'O'){
                dfsBorder(board, i, 0);
            }
            if(board[i][COL-1] == 'O'){
                dfsBorder(board, i, COL-1);
            }
        }

        // 上下边界
        for(int j=0; j<COL; j++){
            if(board[0][j] == 'O'){
                dfsBorder(board, 0, j);
            }
            if(board[ROW-1][j] == 'O'){
                dfsBorder(board, ROW-1, j);
            }
        }

        // O -> X and N -> O
        for(int i=0; i<ROW; i++){
            for(int j=0; j<COL; j++){
                // 剩下来的O 必被X围绕 -> 标记为X
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
                // 新标记的N 未被X围绕 -> 还原为O
                if(board[i][j] == 'N'){
                    board[i][j] = 'O';
                }
            }
        }

        return board;
    }

    /**
     * dfs(边界)
     * @param board
     * @param x
     * @param y
     */
    private void dfsBorder(char[][] board, int x, int y){
        // N: NO
        if(board[x][y]=='X' || board[x][y]=='N'){
            return;
        }

        // O -> N
        board[x][y] = 'N';

        int nextX, nextY;
        for(int i=0; i<4; i++){
            nextX = x+dx[i];
            nextY = y+dy[i];
            if(isValid(nextX, nextY)){
                dfsBorder(board, nextX, nextY);
            }
        }
    }

    /**
     * 模拟法: 边界递归(由外向内) [简化]
     * @param board
     * @return
     */
    private char[][] solution22(char[][] board){
        ROW = board.length;
        COL = board[0].length;

        // 左右边界
        for(int i=0; i<ROW; i++){
            if(board[i][0] == 'O'){
                checkBorder(board, i, 0);
            }
            if(board[i][COL-1] == 'O'){
                checkBorder(board, i, COL-1);
            }
        }

        // 上下边界
        for(int j=0; j<COL; j++){
            if(board[0][j] == 'O'){
                checkBorder(board, 0, j);
            }
            if(board[ROW-1][j] == 'O'){
                checkBorder(board, ROW-1, j);
            }
        }

        // O -> X and N -> O
        for(int i=0; i<ROW; i++){
            for(int j=0; j<COL; j++){
                // 剩下来的O 必被X围绕 -> 标记为X
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
                // 新标记的N 未被X围绕 -> 还原为O
                else if(board[i][j] == 'N'){
                    board[i][j] = 'O';
                }
            }
        }

        return board;
    }

    /**
     * dfs(边界)
     * @param board
     * @param x
     * @param y
     */
    private void checkBorder(char[][] board, int x, int y){
        // 不合法 或者 非O
        if(!isValid(x, y) || board[x][y]!='O'){
            return;
        }

        // O -> N
        board[x][y] = 'N';

        // up
        checkBorder(board, x-1, y);
        // down
        checkBorder(board, x+1, y);
        // left
        checkBorder(board, x, y-1);
        // right
        checkBorder(board, x, y+1);
    }

    /**
     * 模拟法: 边界bfs(由外向内)
     * @param board
     * @return
     */
    private char[][] solution3(char[][] board){
        ROW = board.length;
        COL = board[0].length;

        Queue<int[]> queue = new LinkedList<>();

        // 左右边界
        for(int i=0; i<ROW; i++){
            if(board[i][0] == 'O'){
                queue.offer(new int[]{i,0});
                board[i][0] = 'N';
            }
            if(board[i][COL-1] == 'O'){
                queue.offer(new int[]{i,COL-1});
                board[i][COL-1] = 'N';
            }
        }

        // 上下边界
        for(int j=0; j<COL; j++){
            if(board[0][j] == 'O'){
                queue.offer(new int[]{0,j});
                board[0][j] = 'N';
            }
            if(board[ROW-1][j] == 'O'){
                queue.offer(new int[]{ROW-1,j});
                board[ROW-1][j] = 'N';
            }
        }

        int[] cur;
        int x,y,nx,ny;
        while(!queue.isEmpty()){
            cur = queue.poll();
            x = cur[0];
            y = cur[1];
            for(int i=0; i<4; i++){
                nx = x+dx[i];
                ny = y+dy[i];
                if(isValid(nx,ny) && board[nx][ny]=='O'){
                    queue.offer(new int[]{nx, ny});
                    board[nx][ny] = 'N';
                }
            }
        }

        // O -> X and N -> O
        for(int i=0; i<ROW; i++){
            for(int j=0; j<COL; j++){
                // 剩下来的O 必被X围绕 -> 标记为X
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
                // 新标记的N 未被X围绕 -> 还原为O
                else if(board[i][j] == 'N'){
                    board[i][j] = 'O';
                }
            }
        }

        return board;
    }

    /**
     * 是否合法(是否越界)
     * @param x
     * @param y
     * @return
     */
    private boolean isValid(int x, int y){
        if(x<0 || x>=ROW || y<0 || y>=COL){
            return false;
        }

        return true;
    }

    /**
     * 模拟法: 并查集
     * @param board
     * @return
     */
    private char[][] solution4(char[][] board){
        ROW = board.length;
        COL = board[0].length;

        // 边界O的父节点都是虚拟节点root
        UnionFind uf = new UnionFind(ROW*COL+1);
        int root = ROW*COL;

        for(int i=0; i<ROW; i++){
            for(int j = 0; j < COL; j++){
                // 遇到O 进行并查集合并
                if(board[i][j] == 'O'){
                    // 边界O 与 虚拟节点root 合并成一个连通区域
                    if(i==0 || i==ROW-1 || j==0 || j==COL-1){
                        uf.union(loc(i, j), root);
                    }
                    // 非边界 与上下左右合并成一个连通区域
                    else{
                        // up
                        if(i>0 && board[i-1][j]=='O'){
                            uf.union(loc(i, j), loc(i-1, j));
                        }
                        // down
                        if(i<ROW-1 && board[i+1][j]=='O'){
                            uf.union(loc(i, j), loc(i+1, j));
                        }
                        // left
                        if(j>0 && board[i][j-1]=='O'){
                            uf.union(loc(i, j), loc(i, j-1));
                        }
                        // right
                        if(j<COL-1 && board[i][j+1] =='O'){
                            uf.union(loc(i, j), loc(i, j+1));
                        }
                    }
                }
            }
        }

        for(int i=0; i<ROW; i++){
            for(int j=0; j<COL; j++){
                // 与虚拟节点root 在一个连通区域 -> 未被X围绕
                if(uf.isConnected(loc(i, j), root)){
                    board[i][j] = 'O';
                }
                // 与虚拟节点root 不在在一个连通区域 -> 可被X围绕
                else{
                    board[i][j] = 'X';
                }
            }
        }

        return board;
    }

    /**
     * 坐标位置: 二维转一维(等价于一个结点)
     * @param i
     * @param j
     * @return
     */
    private int loc(int i, int j){
        return i*COL+j;
    }

    /**
     * 并查集类
     */
    private class UnionFind{
        // 连通分量
        int connect;
        // 记录父节点
        int[] parent;

        // 构造函数 n为结点个数
        UnionFind(int n){
            // 初始连通分量
            this.connect = n;
            this.parent = new int[n];
            for(int i=0; i<n; i++){
                // 初始父节点指向自己
                parent[i]=i;
            }
        }

        // 找到x的根节点
        int find(int x){
            while(parent[x] != x){
                // 显著提高效率(减少搜索深度 更快找到根节点)
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        // 连通p和q
        void union(int p, int q){
            int rootP = find(p);
            int rootQ = find(q);
            if(rootP != rootQ){
                parent[rootP] = rootQ;
                connect--;
            }
        }

        // 返回连通分量
        int connect(){
            return connect;
        }

        // 是否连通
        boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }
    }
}

这题要维护一个标记数组，将与边界O联通的O全部标记为“不被包围”，而M本身可视作“被包围”，从而有利于判断未被标记的O“被包围”产生积极影响。然后遍历中间矩阵中的每个未被标记的O，其四周是否都“被包围”，是则将其改为M，否则标记其为“不被包围”。

总的来说还是时间复杂度为O(n^2)的暴力解法。

另外，这题用并查集是个什么思路？我看标签上有提到。

class Solution:
    def surroundedArea(self , board: List[List[str]]) -> List[List[str]]:
        m = len(board)
        n = len(board[0])
        flag = []
        for _ in range(m):
            flag.append([0] * n)
        for i in range(n):
            if board[0][i] == 'O':
                for j in range(m):
                    if board[j][i] == 'X' or flag[j][i] == -1:
                        break
                    flag[j][i] = -1
            if board[m - 1][i] == 'O':
                for j in range(m - 1, 0, -1):
                    if board[j][i] == 'X' or flag[j][i] == -1:
                        break
                    flag[j][i] = -1
        for i in range(m):
            if board[i][0] == 'O':
                for j in range(n):
                    if board[i][j] == 'X' or flag[i][j] == -1:
                        break
                    flag[i][j] = -1
            if board[i][n - 1] == 'O':
                for j in range(n - 1, 0, -1):
                    if board[i][j] == 'X' or flag[i][j] == -1:
                        break
                    flag[i][j] = -1
        for i in range(1, m - 1):
            for j in range(1, n - 1):
                if board[i][j] == 'O' and flag[i][j] == 0:
                    if flag[i - 1][j] == 0 and flag[i + 1][j] == 0 and flag[i][j + 1] == 0 and flag[i][j - 1] == 0:
                        board[i][j] = 'X'
                    else:
                        flag[i][j] = -1
        return board

from operator import le
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param board char字符型二维数组 
# @return char字符型二维数组
#
class Solution:
    def surroundedArea(self , board: List[List[str]]) -> List[List[str]]:
        # write code here
        width = len(board[0])
        height = len(board)

        m = [[0 for i in range(width)] for j in range(height)]

        next_group = 1
        res_gourp = set()

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 'X':
                    continue

                # 已经被标记组别
                if m[i][j] < next_group and m[i][j] != 0:
                    continue
                else:
                    res_gourp.add(next_group)
                    # 开始使用dfs标记组别
                    self.dfs(board, i, j, next_group, m)
                    next_group += 1
        
        # 绕圈一周
        for i in range(width):
            if m[0][i] in res_gourp:
                res_gourp.remove(m[0][i])

        for i in range(height):
            if m[i][0] in res_gourp:
                res_gourp.remove(m[i][0])

        for i in range(width):
            if m[height-1][i] in res_gourp:
                res_gourp.remove(m[height-1][i])

        for i in range(height):
            if m[i][width-1] in res_gourp:
                res_gourp.remove(m[i][width-1])

        for i in range(len(board)):
            for j in range(len(board[0])):
                if m[i][j] in res_gourp:
                    board[i][j] = 'X'

        return board

    def dfs(self, board, x,y, now_group, m):
        if board[x][y] == 'X':
            return
        if m[x][y] == now_group:
            return
        m[x][y] = now_group

        if x > 1:
            self.dfs(board, x-1,y,now_group,m)

        if y > 1:
            self.dfs(board, x,y-1,now_group,m)

        if x < len(m) - 1:
            self.dfs(board, x + 1,y,now_group,m)

        if y < len(m[0]) - 1:
            self.dfs(board, x,y + 1,now_group,m)

struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param board char字符型二维数组 
        * @return char字符型二维数组
    */
    pub fn surroundedArea(&self, board: Vec<Vec<char>>) -> Vec<Vec<char>> {
        // write code here
        use std::iter;
        let mut new_board = Vec::new();
        let n = board[0].len();
        new_board.push(iter::repeat('O').take(n + 2).collect::<Vec<_>>());
        for mut i in board.into_iter() {
            let mut v = vec!['O'];
            v.append(&mut i);
            v.push('O');
            new_board.push(v);
        }
        new_board.push(iter::repeat('O').take(n + 2).collect::<Vec<_>>());
        let mut board = new_board;
        let m = board.len();
        let n = board[0].len();
        let is_valid = |(x, y): (isize, isize)| {
            x >= 0 && y >= 0 && x < m as isize && y < n as isize
        };

        depth_first_traversal(&mut board, (0, 0), &is_valid);
        
        for i in 0 .. m {
            for j in 0 .. n {
                board[i][j] = if board[i][j] == 'O' {'X'} else {board[i][j]};
            }
        }
        for i in 0 .. m {
            for j in 0 .. n {
                board[i][j] = if board[i][j] == 'Z' {'O'} else {board[i][j]};
            }
        }
        // println!("{:?}", board);
        
        board[1 .. m - 1].into_iter().map(|i| i[1 .. n - 1].into_iter().map(|c| *c).collect::<Vec<_>>()).collect::<Vec<Vec<char>>>()
    }
}

fn depth_first_traversal<F>(board: &mut Vec<Vec<char>>, pos: (isize, isize), is_valid: &F) -> () where F: Fn((isize, isize)) -> bool {
    if is_valid(pos) && board[pos.0 as usize][pos.1 as usize] == 'O' {
        board[pos.0 as usize][pos.1 as usize] = 'Z';
        let dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)];
        for dir in dirs.iter() {
            depth_first_traversal(board, (pos.0 + dir.0, pos.1 + dir.1), is_valid);
        }
    }
}

思路：递归解题。二重循环遍历矩阵，如果为O那么递归寻找左右上下的O，如果能找到边界，那么该相邻的O均没有被围绕，因此不能填充。如果没有找到边界，说明延申的O均被围绕，需要填充。
初版代码：

import java.util.*;
public class Solution {
    public char[][] surroundedArea (char[][] board) {
        for(int i = 1; i < board.length - 1; ++i) {
            for(int j = 1; j < board[i].length - 1; ++j) {
                judge(board, i, j);
            }
        }
        return board;
    }
    public boolean judge(char[][] board, int i, int j) {
        if(i > 0 && i < board.length - 1 && j > 0 && j < board[i].length - 1 && board[i][j] == 'O') {
            board[i][j] = 'X';
            boolean left = judge(board, i, j + 1);
            boolean right = judge(board, i, j - 1);
            boolean up = judge(board, i + 1, j);
            boolean down = judge(board, i - 1, j);
            if(left && right && up && down) {
                return true;
            }
            board[i][j] = 'O';
            return false;
        } 
        if((i == 0 || i == board.length - 1 || j == 0 || j == board[i].length - 1) && board[i][j] == 'O')
            return false;
        return true;
    }
}

值得注意的是，如果整个矩阵都是O，那么将会重复递归多次，因此可以采用记忆化手段：把没有被围绕的O做上标记，避免下次继续递归。

import java.util.*;
public class Solution {
    public char[][] surroundedArea (char[][] board) {
        boolean dp[][] = new boolean[board.length][board[0].length];
        for(int i = 1; i < board.length - 1; ++i) {
            for(int j = 1; j < board[i].length - 1; ++j) {
                judge(dp, board, i, j);
            }
        }
        return board;
    }
    public boolean judge(boolean [][]dp, char[][] board, int i, int j) {
        if(i > 0 && i < board.length - 1 && j > 0 && j < board[i].length - 1 && board[i][j] == 'O' && !dp[i][j]) {
            board[i][j] = 'X';
            boolean left = judge(dp, board, i, j + 1);
            boolean right = judge(dp, board, i, j - 1);
            boolean up = judge(dp, board, i + 1, j);
            boolean down = judge(dp, board, i - 1, j);
            if(left && right && up && down) {
                return true;
            }
            board[i][j] = 'O';
            dp[i][j] = true;
            return false;
        } 
        if((i == 0 || i == board.length - 1 || j == 0 || j == board[i].length - 1) && board[i][j] == 'O')
            return false;
        return true;
    }
}

正着思考从中间搜'O'然后判断是否被包围很麻烦，因此反向思考，直接从边界上的'O'开始，把和边界上的'O'连通的'O'全部标记一遍。最后把没有标记的'O'替换为'X'即可。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型二维数组 
     * @return char字符型二维数组
     */
     boolean[][] vis ;
     int row;
     int col;
    public char[][] surroundedArea (char[][] board) {
        // write code here
        row = board.length;
        col = board[0].length;
        boolean[][] flag = new boolean[row][col];
        vis = new boolean[row][col];
        for(int i=0;i<col;i++){
            if(board[0][i] == 'O'){
                dfs(board,0,i);
            }
        }
        for(int i=0;i<row;i++){
            if(board[i][0] == 'O'){
                dfs(board,i,0);
            }
        }
        for(int i=0;i<row;i++){
            if(board[i][col - 1] == 'O'){
                dfs(board,i,col - 1);
            }
        }

        for(int i=0;i<col;i++){
            if(board[row - 1][i] == 'O'){
                dfs(board,row - 1,i);
            }
        }

        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(board[i][j] == 't'){
                    board[i][j] = 'O';
                }
            }
        }
        return board;

    }

    int[] dist = new int[]{0,1,0,-1,0};
    public void dfs(char[][] board,int i,int j){
        vis[i][j] = true;
        board[i][j] = 't';

        for(int k=0;k<=3;k++){
            int new_x = i + dist[k];
            int new_y = j + dist[k + 1];
            if(new_x >= 0 && new_x < row && new_y >= 0 && new_y < col && !vis[new_x][new_y] && board[new_x][new_y] == 'O'){
                dfs(board,new_x,new_y);
            }
        }

    }
}

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param board char字符型二维数组 
 * @return char字符型二维数组
*/
func surroundedArea( board [][]byte ) [][]byte {
    n,m:=len(board),len(board[0])
    var dfs func(int,int)
    dfs=func(i,j int){
        if i<0||i>=n||j<0||j>=m||board[i][j]!='O'{
            return
        }
        board[i][j]='y'
        dfs(i+1,j)
        dfs(i-1,j)
        dfs(i,j+1)
        dfs(i,j-1)
    }
    for i:=0;i<m;i++{
        if board[0][i]=='O'{
            dfs(0,i)
        }
        if board[n-1][i]=='O'{
            dfs(n-1,i)
        }
    }
    for i:=0;i<n;i++{
        if board[i][0]=='O'{
            dfs(i,0)
        }
        if board[i][m-1]=='O'{
            dfs(i,m-1)
        }
    }
    for i:=0;i<n;i++{
        for j:=0;j<m;j++{
            if board[i][j]=='O'{
                board[i][j]='X'
            }
        }
    }
    for i:=0;i<n;i++{
        for j:=0;j<m;j++{
            if board[i][j]=='y'{
                board[i][j]='O'
            }
        }
    }
    return board
}

int[] dx = {0,1,0,-1};
    int[] dy = {1,0,-1,0};
    public char[][] surroundedArea (char[][] board) {
        // write code here
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                dfs(board,i,0);
            }
            if (board[i][n - 1] == 'O') {
                dfs(board,i,n-1);
            }
        }
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {
                dfs(board,0,i);
            }
            if (board[m-1][i] == 'O') {
                dfs(board,m-1,i);
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
                if(board[i][j] == 'L'){
                    board[i][j] = 'O';
                }
            }
        }
        return board;
    }
        //dfs方法：深度搜索与每一个边界O字符相邻的O字符区域（对应深度优先算法思想中搜索到底的一条单独的路经）
//，将其改为L字符
    public void dfs(char[][] board,int i,int j){
        board[i][j] = 'L';
        for(int k=0;k<4;k++){
            int x = i+dx[k];
            int y = j+dy[k];
            if(x>=0 && x<board.length && y>=0 && y<board[0].length && board[x][y] == 'O'){
                dfs(board,x,y);
            }
        }
    }

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param board char字符型二维数组 
 * @return char字符型二维数组
*/
func surroundedArea(board [][]byte) [][]byte {
	// write code here
	n := len(board)
	m := len(board[0])

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if board[i][j] == 'O' {
				bfs(&board, i, j, n, m)
			}
		}
	}

	return board
}

func bfs(board *[][]byte, x, y int, n, m int) {
	queue := [][2]int{{x, y}} // 初始化把当前坐标加入队列
	currentO := [][2]int{}

	for len(queue) > 0 {
		front := queue[0]
		currentO = append(currentO, front)
		queue = queue[1:]
		i, j := front[0], front[1]
		(*board)[i][j] = 'T'
		if i-1 >= 0 && (*board)[i-1][j] == 'O' {
			queue = append(queue, [2]int{i - 1, j})
		}
		if i+1 < n && (*board)[i+1][j] == 'O' {
			queue = append(queue, [2]int{i + 1, j})
		}
		if j-1 >= 0 && (*board)[i][j-1] == 'O' {
			queue = append(queue, [2]int{i, j - 1})
		}
		if j+1 < m && (*board)[i][j+1] == 'O' {
			queue = append(queue, [2]int{i, j + 1})
		}
	}
	canChange := true
	for i := 0; i < len(currentO); i++ {
		if currentO[i][0] == 0 || currentO[i][0] == n-1 || currentO[i][1] == 0 || currentO[i][1] == m-1 {
			canChange = false
		}
	}
	if canChange {
		for i := 0; i < len(currentO); i++ {
			(*board)[currentO[i][0]][currentO[i][1]] = 'X'
		}
	} else {
		for i := 0; i < len(currentO); i++ {
			(*board)[currentO[i][0]][currentO[i][1]] = 'O'
		}
	}
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param board char字符型二维数组 
# @return char字符型二维数组
#
class Solution:
    def dfs(self, num, i, j):
        if num[i][j] == 'O':
            num[i][j] = 1
            x1 = [0,0,1,-1]
            y1 = [1,-1,0,0]
            for k in range(4):
                x = x1[k]+i 
                y = y1[k]+j
                if 0 <= x < len(num) and 0 <= y < len(num[0]) and num[x][y] == 'O':
                    self.dfs(num, x, y)
        return num
    
    
    def surroundedArea(self , board: List[List[str]]) -> List[List[str]]:
        m = len(board)
        n = len(board[0])
        if m > 2 and n > 2:
            for i in range(m):
                for j in range(n):
                    if i == 0&nbs***bsp;j == 0&nbs***bsp;i == m-1&nbs***bsp;j == n-1:
                        board = self.dfs(board, i, j)
            for i in range(m):
                for j in range(n):
                    if board[i][j] == 1:
                        board[i][j] = 'O'
                    else:
                        board[i][j] = 'X'
            return board
        else:
            return board

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @return char字符型vector<vector<>>
     */
    vector<vector<char> > surroundedArea(vector<vector<char> >& board) {
        // write code here
        //先搜索边界上以及与边界相连的所有圆，标记为*进行保护
        //然后把剩余的圆置为x，最后把所有*恢复成圆
        for(int i=0;i<board.size();i++)//先从边界开始搜索，保护边界上的圆
        {
            searchedge(board, i, 0, true);
            searchedge(board, i, board[0].size()-1, true);
        }
        for(int j=0;j<board[0].size();j++)
        {
            searchedge(board, 0, j, true);
            searchedge(board, board.size()-1, j,true);
        }
        for(int i=1;i<board.size()-1;i++)
        {
            for(int j=1;j<board[0].size()-1;j++)
            {
                searchedge(board, i, j, false);
            }
        }
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[0].size();j++)
            {
                if(board[i][j]=='1')
                {
                    board[i][j]='X';
                }
                else
                {
                    board[i][j]='O';
                }
            }
        }
        return board;
    }
    void searchedge(vector<vector<char>> &board,int x,int y,bool edge)
    {
        if(x<0||y<0||x>=board.size()||y>=board[0].size())
        {
            return;
        }
        if(board[x][y]!='X'&&board[x][y]!='O')//访问过
        {
            return;
        }
        if(edge)
        {
            if(board[x][y]=='X')
            {
                board[x][y]='1';//访问标记
            }
            else//'O'
            {
                board[x][y]='*';
                searchedge(board, x+1, y, true);
                searchedge(board, x-1, y, true);
                searchedge(board, x, y+1, true);
                searchedge(board, x, y-1, true);
            }
        }
        else
        {
            board[x][y]='1';//访问标记
        }
    }

};

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * NC226 被围绕的区域
 */
public class Solution226 {

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param board char字符型二维数组
     * @return char字符型二维数组
     */
    public char[][] surroundedArea(char[][] board) {
        // write code here
        int length1 = board.length;
        int length2 = board[0].length;
        Queue<Integer> queue1 = new LinkedList<>();
        Queue<Integer> queue2 = new LinkedList<>();
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();

        for (int i = 0; i < length1; i++) {
            for (int j = 0; j < length2; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';

                    int num = 0;
                    boolean flag = true;
                    queue1.add(i);
                    stack1.add(i);
                    queue2.add(j);
                    stack2.add(j);

                    while (!queue1.isEmpty()) {
                        int poll1 = queue1.poll();
                        int poll2 = queue2.poll();
                        num++;
                        flag &= poll1 != 0 && poll1 != length1 - 1 && poll2 != 0 && poll2 != length2 - 1;
                        if (poll1 > 0 && board[poll1 - 1][poll2] == 'O') {
                            board[poll1 - 1][poll2] = 'X';
                            queue1.add(poll1 - 1);
                            stack1.add(poll1 - 1);
                            queue2.add(poll2);
                            stack2.add(poll2);
                        }
                        if (poll1 < length1 - 1 && board[poll1 + 1][poll2] == 'O') {
                            board[poll1 + 1][poll2] = 'X';
                            queue1.add(poll1 + 1);
                            stack1.add(poll1 + 1);
                            queue2.add(poll2);
                            stack2.add(poll2);
                        }
                        if (poll2 > 0 && board[poll1][poll2 - 1] == 'O') {
                            board[poll1][poll2 - 1] = 'X';
                            queue1.add(poll1);
                            stack1.add(poll1);
                            queue2.add(poll2 - 1);
                            stack2.add(poll2 - 1);
                        }
                        if (poll2 < length2 - 1 && board[poll1][poll2 + 1] == 'O') {
                            board[poll1][poll2 + 1] = 'X';
                            queue1.add(poll1);
                            stack1.add(poll1);
                            queue2.add(poll2 + 1);
                            stack2.add(poll2 + 1);
                        }
                    }

                    if (flag) {
                        while (num > 0) {
                            num--;
                            stack1.pop();
                            stack2.pop();
                        }
                    }
                }


            }
        }

        while (!stack1.isEmpty()) {
            board[stack1.pop()][stack2.pop()] = 'O';
        }
        return board;
    }


    public char[][] surroundedArea1(char[][] board) {
        // write code here
        int length1 = board.length;
        int length2 = board[0].length;
        for (int i = 0; i < length1; i++) {
            dfs(board, i, 0, length1, length2);
            dfs(board, i, length2 - 1, length1, length2);
        }
        for (int j = 1; j < length2 - 1; j++) {
            dfs(board, 0, j, length1, length2);
            dfs(board, length1 - 1, j, length1, length2);
        }
        for (int i = 0; i < length1; i++) {
            for (int j = 0; j < length2; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == 'Y') {
                    board[i][j] = 'O';
                }
            }
        }
        return board;
    }

    private void dfs(char[][] board, int i, int j, int length1, int length2) {
        if (i < 0 || i >= length1 || j < 0 || j >= length2 || board[i][j] != 'O') {
            return;
        }
        board[i][j] = 'Y';
        dfs(board, i + 1, j, length1, length2);
        dfs(board, i - 1, j, length1, length2);
        dfs(board, i, j + 1, length1, length2);
        dfs(board, i, j - 1, length1, length2);
    }
}

class Solution:
    def surroundedArea(self , board: List[List[str]]) -> List[List[str]]:
        # write code here
        m,n=len(board),len(board[0])
        def dfs(i,j):
            if (i<0&nbs***bsp;i>m-1)&nbs***bsp;(j<0&nbs***bsp;j>n-1)&nbs***bsp;board[i][j]!="O":
                return
            if board[i][j]=="O":
                board[i][j]="No"
            dfs(i-1,j)
            dfs(i+1,j)
            dfs(i,j-1)
            dfs(i,j+1)
        for i in range(m):
            dfs(i,0)
            dfs(i,n-1)
        
        for j in range(n):
            dfs(0,j)
            dfs(m-1,j)
        for i in range(m):
            for j in range(n):
                if board[i][j]=="O":
                    board[i][j]="X"
                elif board[i][j]=="No":
                    board[i][j]="O"
        return board