130. 被围绕的区域(leetcode)

LXL's Blog / 2024-10-07 / 原文

https://leetcode.cn/problems/surrounded-regions/

class Solution {
    int n;
    int m;
    boolean[][] vis;
    char[][] board;
    int[] dx=new int[]{0,1,0,-1};
    int[] dy=new int[]{1,0,-1,0};
    public void solve(char[][] board) {
        // 从边缘O出发,通过flood fill,标记和边缘相连的联通块,再把剩余区域标记为X
        n=board.length;
        m=board[0].length;
        vis=new boolean[n][m];
        this.board=board;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                // 边缘的点满足性质: x==0||n-1 或者 y==0||m-1
                if(i!=0 && i!=n-1 &&  j!=0 && j!=m-1)continue;
                if(board[i][j]=='O' && vis[i][j]==false)
                {
                    dfs(i,j);
                }
            }
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                if(vis[i][j]==false && board[i][j]=='O')board[i][j]='X';
            }
    }  

    void dfs(int x,int y)
    {
        vis[x][y]=true;
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a>=0 && b>=0 && a<n && b<m && vis[a][b]==false && board[a][b]=='O')
            {
                dfs(a,b);
            }
        }
    }

}