leetcode-130 被围绕的区域

题目描述：给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

代码实现

连通图实现

public class UF {
    /**
     * 子树个数
     */
    private int count;

    /**
     * 记录每个节点的父节点
     */
    private int[] parent;

    /**
     * 记录每个节点的子树的节点个数
     */
    private int[] size;

    /**
     * 初始化构造函数
     *
     * @param n 子树初始节点个数
     */
    public UF(int n) {
        this.count = n;
        this.parent = new int[n];
        this.size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    /**
     * 合并两颗子树
     *
     * @param p 节点p
     * @param q 节点q
     */
    public void union(int p, int q) {
        int pRoot = findRoot(p);
        int qRoot = findRoot(q);
        if (pRoot == qRoot) {
            return;
        }
        if (size[pRoot] > size[qRoot]) {
            parent[qRoot] = pRoot;
            size[pRoot] = size[qRoot] + size[pRoot];

        } else {
            parent[pRoot] = qRoot;
            size[qRoot] = size[pRoot] + size[qRoot];
        }
        count--;
    }

    /**
     * 两个节点是否属于同一颗子树
     *
     * @param p 节点p
     * @param q 节点q
     * @return 是否属于同一颗子树
     */
    public boolean connected(int p, int q) {
        int pRoot = findRoot(p);
        int qRoot = findRoot(q);
        return pRoot == qRoot;
    }

    /**
     * 找到当前节点的根节点
     *
     * @param x 当前节点
     * @return 根节点
     */
    private int findRoot(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    /**
     * 返回当前子树个数
     *
     * @return 个数
     */
    public int count() {
        return this.count;
    }
}

class Solution {
    public void solve(char[][] board) {
        //1. 判空
        if (board == null || board.length == 0) {
            return;
        }

        //2. 初始化连通图
        int m = board.length;
        int n = board[0].length;
        UF uf = new UF(m * n + 1);

        //3. 假设有个m*n节点，视为非包围O节点的根节点
        int dummy = m * n;

        //4. 处理前后两列
        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);
            }
        }

        //5. 处理上下两行
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                uf.union(j, dummy);
            }
            if (board[m - 1][j] == 'O') {
                uf.union((m - 1) * n + j, dummy);
            }
        }

        //6. 处理每个非边缘节点
        int[][] dp = new int[][]{{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') {
                    int p = i * n + j;
                    for (int k = 0; k < 4; k++) {
                        int x = i + dp[k][0];
                        int y = j + dp[k][1];
                        if (board[x][y] == 'O') {
                            int q = x * n + y;
                            uf.union(p, q);
                        }
                    }
                }
            }
        }

        //7. 根据结果处理数组
        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';
                }
            }
        }
    }
}