Leetcode 130.被围绕的区域

深度遍历

• 只从边界 ‘0’ 开始遍历，就不用考虑如何恢复没符合条件的标记

class Solution {
    public void solve(char[][] board) {
        int n = board.length;
        if(n == 0)
            return;

        int m = board[0].length;

        /*
            只从矩阵的边界深度遍历，标记和边界 '0' 有联系的'0'
         */
        for(int i = 0; i < n; i++){
            dfs(i, 0, board);
            dfs(i, m - 1, board);
        }

        for(int i = 1; i < m - 1; i++){
            dfs(0, i, board);
            dfs(n - 1, i, board);
        }

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

    /**
     * 深度遍历，将遇到的 '0' 标记为 'A'
     * @param i
     * @param j
     * @param board
     */
    public void dfs(int i, int j, char[][] board){
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length
                || board[i][j] == 'X' || board[i][j] == 'A')
            return;

        board[i][j] = 'A';
        dfs(i + 1, j,  board);
        dfs(i, j + 1,  board);
        dfs(i - 1 , j,  board);
        dfs(i, j - 1,  board);
    }
}

并查集

并查集

class Solution {
    class UnionFind {
        private int[] parent;  // 父结点在数组里的索引
        private int[] rank;     // 结点所在树的深度

        /**
        * 初始化，父结点指向自己
        * @param size  结点个数
        */
        public UnionFind(int size){
            parent = new int[size];
            rank = new int[size];
            for(int i = 0; i < size; i++){
                parent[i] = i;
                rank[i] = 1;
            }
        }

        /**
        * 递归查询结点所在树最终的根节点
        * @param x
        * @return
        */
        public int find(int x){
    //        if(parent[x] == x){
    //            return x;
    //        } else {
    //            parent[x] = find(parent[x]);
    //            return parent[x];
    //        }

            return parent[x] == x ? x : (parent[x] = find(parent[x]));
        }

        /**
        * 按深度合并，深度小的合并到深度大的树里面去
        * @param x
        * @param y
        */
        public void merge(int x, int y){
            int xParent = find(x), yParent = find(y);
            if (rank[xParent] <= rank[yParent]){
                parent[xParent] = yParent;
            } else {
                parent[yParent] = xParent;
            }

            // 如果两个根节点不同，深度相同，第一个if已经将 x 所在
            // 的树合并到 y 所在的树，所以 y 树深度应该加1
            if(rank[xParent] == rank[yParent] && xParent != yParent){
                rank[yParent]++;
            }
        }


        /**
        * 判断两个结点是不是联通的，即是不是在同一个集合（树）内
        * @param x
        * @param y
        * @return
        */
        public boolean isConnected(int x, int y){
            return find(x) == find(y);
        }
    }
    public void solve(char[][] board) {
        int n = board.length;
        if(n == 0)
            return;

        int m = board[0].length;

        UnionFind uf = new UnionFind(n * m + 1);
        // 虚拟结点，所有边界 '0' 的最终根结点
        int dummyNode = n * m;

        for (int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(board[i][j] == 'O'){
                    // 边界 '0' 的最终根结点是虚拟结点dummyNode
                    if(i == 0 || i == n - 1 || j == 0 || j == m - 1)
                        uf.merge(node(i, j, m), dummyNode);
                    else {
                        // 上下左右连通
                        if(i + 1 < n && board[i + 1][j] == 'O'){
                            uf.merge(node(i + 1, j, m), node(i, j, m));
                        }
                        if(i - 1 >= 0 && board[i - 1][j] == 'O'){
                            uf.merge(node(i - 1, j, m), node(i, j, m));
                        }
                        if(j + 1 < m && board[i][j + 1] == 'O'){
                            uf.merge(node(i, j + 1, m), node(i, j, m));
                        }
                        if(j - 1 >= 0 && board[i][j - 1] == 'O'){
                            uf.merge(node(i, j - 1, m), node(i, j, m));
                        }
                    }
                }
            }
        }

        for(int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (board[i][j] == 'O' && !uf.isConnected(node(i , j ,m), dummyNode)){
                    board[i][j] = 'X';
                }
            }
        }
    }

    /**
     * 二维坐标转换为一维坐标
     * @param i
     * @param j
     * @param m  矩阵的列秩 (列数)
     * @return
     */
    public int node(int i, int j, int m){
        return i * m + j;
    }
}

最后

以上就是阔达冬天为你收集整理的Leetcode130Surrounded Regions深度遍历并查集的全部内容，希望文章能够帮你解决Leetcode130Surrounded Regions深度遍历并查集所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。