Leetcode 130

public void dfs(char[][] board){
        int n = board.length;
        if (n == 0){
            return;
        }
        //n为行数,m为列数
        int m = board[0].length;

        //找出左右边界上的O，改为A
        for (int i = 0; i < n; i++) {
            dfs(board , i , 0);
            dfs(board , i , m - 1);
        }

        //找出上下边界的O改为A
        for (int i = 1; i < m - 1; i++) {
            dfs(board , 0 , i);
            dfs(board , n - 1 , i);
        }

        //遍历
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'A'){
                    board[i][j] = 'O';
                }else if (board[i][j] == 'O'){
                    board[i][j] = 'X';
                }else {
                    continue;
                }
            }
        }
    }

    //若找到边界上的O，开始上下左右搜索
    //将邻接的O也变成A
    public c void dfs(char[][] board , int x , int y){
        //越界处理，以及寻O
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length || board[x][y] != 'O'){
            return;
        }
        board[x][y] = 'A';
        //上下左右搜索
        dfs(board , x + 1 , y);
        dfs(board , x - 1 , y);
        dfs(board , x , y + 1);
        dfs(board , x , y - 1);
    }

public void solve(char[][] board) {
        if (board.length == 0){
            return;
        }

        int m = board.length;
        int n = board[0].length;
        UnionFind uf = new UnionFind(m * n + 1);
        //虚构一个节点去连接
        int dummy = m * n ;

        //将首列和末列的O与dummy连接
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O'){
                uf.union(i * n , dummy);
            }
            if (board[i][n - 1] == 'O'){
                uf.union(i * n + n - 1 , dummy);
            }
        }

        // 将首行和末行的 O 与 dummy 连通
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                uf.union(j, dummy);
            }
            if (board[m - 1][j] == 'O') {
                uf.union(n * (m - 1) + j, dummy);
            }
        }

        // 方向数组 direction 是上下左右搜索的常用手法
        int[][] direction = {{1,0}, {0,1}, {0,-1}, {-1,0}};
        for (int i = 1; i <  m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (board[i][j] == 'O'){
                    for (int k = 0; k < 4; k++) {
                        int x = i + direction[k][0];
                        int y = j + direction[k][1];
                        if (board[x][y] == 'O') {
                            uf.union(x * n + y , i * n + j);
                        }
                    }
                }
            }
        }

        //不和dummy连通的O，都要替换成X
        for (int i = 1; i <  m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (!uf.connected(dummy , i * n + j)){
                    board[i][j] = 'X';
                }
            }
        }
    }