1.题目

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

示例 1：

输入：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’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：
输入：board = “X”
输出：“X”

提示：
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 ‘X’ 或 ‘O’

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/surrounded-regions

2.思路

（1）并查集
本题和 LeetCode_DFS_中等_1254. 统计封闭岛屿的数目 这题几乎完全一样，常规做法使用 DFS，这里我们使用另一种算法——并查集算法。并查集的思路参考并查集（UNION-FIND）算法详解。

3.代码实现（Java）

//思路1————并查集
class Solution {
    public void solve(char[][] board) {
        // m 行 n 列的矩阵
        int m = board.length;
        int n = board[0].length;
        /*
            由题分析可知，与矩阵边界相邻的 O 不需要被替换
            假设它们有一个共同根节点叫 dummy，这些 O 和 dummy 互相连通，而那些需要被替换的 O 与 dummy 不连通。
        */
        //给 dummy 留一个额外位置
        UF uf = new UF(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);
            }
        }
        //设置方向数组 d 
        int[][] d = 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') {
                    //将此 'O' 与其上下左右的 'O' 连通
                    for (int k = 0; k < 4; k++) {
                        int x = i + d[k][0];
                        int y = j + d[k][1];
                        if (board[x][y] == 'O') {
                            uf.union(x * n + y, i * n + j);
                        }
                    }
                }
            }
        }
        //替换掉所有不与 dummy 相通的 'O' 
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n; j++) {
                if (!uf.isConnected(dummy, i * n + j)) {
                    board[i][j] = 'X';
                }
            }
        }
    }
}
//并查集
class UF {
    //记录连通分量(树)的个数
    private int count;
    //节点 x 的根节点是 root[x]
    private int[] root;
    //记录每棵树中的节点数
    private int[] size;
    //初始化
    public UF(int n) {
        //初始时每个节点都是一个连通分量
        this.count = n;
        root = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            //初始时每个节点的根节点都是其自己
            root[i] = i;
            size[i] = 1;
        }
    }
    //将 p 和 q 连通
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) {
            // p 和 q 的根节点相同，它们本就是连通的，直接返回即可
            return;
        } else {
            /*
                p 和 q 的根节点不相同，将它们连通
                小树接到大树下面，这样比较平衡
            */
            if (size[rootP] > size[rootQ]) {
                root[rootQ] = rootP;
                size[rootP] += size[rootQ];
            } else {
                root[rootP] = rootQ;
                size[rootQ] += size[rootP];
            }
             count--;
        }
    }
    //判断 p 和 q 是否互相连通
    public boolean isConnected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        //如果 p 和 q 的根节点相同，则说明它们在同一颗树上，即它们是连通的
        return rootP == rootQ;
    }
    //查找节点 x 的根节点
    public int find(int x) {
        while (root[x] != x) {
            //进行路径压缩
            root[x] = root[root[x]];
            x = root[x];
        }
        return x;
    }
    //返回连通分量(树)的个数
    public int getCount() {
        return count;
    }
}