Leetcode每日一题 —— 1559. 二维网格图中探测环

1559. 二维网格图中探测环 - 力扣（LeetCode）

1559. 二维网格图中探测环 - 给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在 相同值 形成的环。 一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值 。 同时，你也不能回到上一次移动时所在的格子。比方说，环  (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从 (1, 2) 移动到 (1, 1)...

思路

比较典型的无向图判环题，常用的思想有 DFS / BFS / 并查集，这里咱就用并查集来做了。

先注意题目中两个条件：

1. 走回头路不算环路，也就不能往回走。
2. 环路径的长度要 \ge 4 才算。其实在第 1 点条件的限制下这点是必然成立的，最小的环必须要有四个格子组成。

所以这题只需要保证不走回头路，进行判环即可。

用并查集判环，要不走回头路的话，我们在扫描网格时从上至下、从左至右，对于每个格子可以只尝试合并其右方或者下方的格子，按这样的逻辑处理必然是不会有回头路滴。

如此扫描直至某个网格与其右边或者下边的网格在同一个集合中，则满足题目要求，返回 true。

代码

class Solution {
public:
    bool containsCycle(vector<vector<char>>& grid) {
        // 比较重要的是这种环路的长度还必须 >=4 才算
        // 其实不难，可以用并查集来执行合并和判环，如果有环就看对应块中元素数量是不是 >=4
        // 要构成环，最小的环必然是四个方格组成的
        int m=grid.size(),n=grid[0].size();

        // 初始化并查集
        vector<int> parents(m*n,-1),sizes(m*n,1);

        auto find=[&](auto&& self, int x) -> int {
            // 带路径压缩的查找
            return parents[x]==-1 ? x : parents[x]=self(self, parents[x]);
        };
        // 合并，返回是否执行了合并
        auto merge=[&](int x1,int x2) -> bool {
            int root1=find(find,x1),root2=find(find,x2);
            if(root1==root2){
                // 已经合并
                return false;
            }
            // 否则启发式合并，小树并入大树
            if(sizes[root1]<sizes[root2]){
                swap(root1,root2);
            }
            parents[root2]=root1;
            sizes[root1]+=sizes[root2];
            return true;
        };
        // 获得集合大小
        // auto getSize=[&](int x){
        //     return sizes[find(find,x)];
        // };

        // 扫描数组执行判环
        int drcts[][2]={
            {0,1},
            {1,0},
        };
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                // 为了防止走回头路，对于每个方格我们只往右或者往下合并
                for(auto& d:drcts){
                    int newI=i+d[0],newJ=j+d[1];
                    if(newI>=m||newJ>=n||grid[newI][newJ]!=grid[i][j]){
                        // 越界或者字母不相同
                        continue;
                    }
                    // 尝试执行合并
                    if(!merge(i*n+j,newI*n+newJ)/*&&getSize(i*n+j)>=4*/){
                        // 如果没有执行合并，说明遇到已经在并查集里的了，有环
                        // 这个时候判断，如果集合中有 >=4 个元素就可以结束
                        // 其实在不走回头路的前提下，只要有环，必然路径长度 >=4 
                        return true;
                    }
                }
            }
        }
        return false;
    }
};

2 个帖子 - 2 位参与者

阅读完整话题