【C++图论 DFS】1559. 二维网格图中探测环|1837

本文涉及知识点

C++图论
C++DFS

LeetCode1559. 二维网格图中探测环

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

示例 1：

输入：grid = [[“a”,“a”,“a”,“a”],[“a”,“b”,“b”,“a”],[“a”,“b”,“b”,“a”],[“a”,“a”,“a”,“a”]]
输出：true
解释：如下图所示，有 2 个用不同颜色标出来的环：

示例 2：

输入：grid = [[“c”,“c”,“c”,“a”],[“c”,“d”,“c”,“c”],[“c”,“c”,“e”,“c”],[“f”,“c”,“c”,“c”]]
输出：true
解释：如下图所示，只有高亮所示的一个合法环：

示例 3：

输入：grid = [[“a”,“b”,“b”],[“b”,“z”,“b”],[“b”,“b”,“a”]]
输出：false

提示：

m == grid.length
n == grid[i].length
1 <= m <= 500
1 <= n <= 500
grid 只包含小写英文字母。

网格

性质一：四连通、八连通单格图没有自环和重边，故没有一个节点或两个节点的环。
性质二：3个相邻（四连通）的单格只有两情况：一行（列）3个，第一行一个第二行两个，都无法构成环。
故 至少4个节点的环    ⟺    \iff ⟺ 环。

连通图（可能有环）

定义一：连通图（可能有环）的层次。选取任意节点root，各节点到root的最短距离就是各节点的层次。显然root的层次是0。
性质一：节点cur的层次是leve，则最短路径的倒数第二个节点一定是leve-1层。否则令其为x层，则cur的层次应该是x+1，与假设矛盾。
操作一：无向连通图转由向连通图。规则：层次小的节点指向层次大，层次相同则节点编号小的指向大的。父节点指向子节点。
性质二：操作一后，root可以访问所有节点。最短路径反向。

树（连通无环无向图）
性质一：如果有n个节点，则一定有n-1条边。以任意节点为根，初始已访问集只有根，其它节点都在未访问集。选择任意一条一个节点在已访问集的边e，如果不存在,说明已访问集未访问集未连通，与定义矛盾。e的另一个节点一定不在已访问集，否则有环。上述操作每条边，都增加一个节点。故增加n-1个节点，需要n-1条边。

经典DFS

对树进行连通图操作一（如果临接点是父节点就忽略）后，DFS(root)。DFS(cur)的大致逻辑：依次DFS cur的孩子。
性质四：每个节点都会被调用到，调用堆栈就是最短路径。
性质五：每个节点都只会被调用一次。无环，故最短路径只有一条，即只有一个父节点。即每条边只被调用一次。n-1条边，DFS共调用n-1次，加上初始调用共n次。
结论一：经典DFS对树，访问所节点一次。

连通图2（可能有环）

结论一：对有环无向图连通图，经典DFS，会死循环，故要提前退出。经典DFS可以判断是否有环，不失一般性，令某环abcda，且第一次访问的是a，则一定会依次访问bcda。如果临接点是父节点就忽略    ⟺    \iff ⟺ 忽略cur的前一个节点和后一个节点相同的路径，最短路径显然不符合。故通过最短路径的反向路径一定能访问到a。

DFS

各单格看做点，4连通且值相同的单格有无向边连接。单独处理各联通区域。连通无环无向图就是树，通过排除父节点，以任何节点为根，都访问且只访问各节点一次。
m_vis[i]记录i节点访问次数。如果vis[i]被访问2次或更多，返回true；否则返回false。
时间复杂度：O(nn)

并集查找

获取各节点的邻接表，用并集查找看各联通区域的节点数，并统计个连通区域的节点数和边数。根据树的性质一，看是否有环。注意：边数ab，被统计了两次，要除以2。

拓扑排序

无法拓扑排序的节点便是环。

代码

核心代码

class Solution {public:bool containsCycle(vector<vector<char>>& grid) {const int R = grid.size();const int C = grid[0].size();const int iMaskCount = R * C;vector<vector<int>> neiBo(iMaskCount);auto Add = [&](int r, int c, int r1, int c1) {if (grid[r][c] != grid[r1][c1]) { return ; }const int m1 = C * r + c;const int m2 = C * r1 + c1;neiBo[m1].emplace_back(m2);neiBo[m2].emplace_back(m1);};for (int r = 0; r < R; r++) {for (int c = 0; c < C; c++) {if (r + 1 < R) {Add(r, c, r + 1, c);}if (c + 1 < C) {Add(r, c, r, c + 1);}}}vector<int> vis(iMaskCount);function<bool(int,int)> DFS = [&](int cur, int par) {vis[cur]++;if (vis[cur] > 1) { return true; }for (const auto& next : neiBo[cur]) {if (next == par) { continue; }if (DFS(next, cur)) { return true; }}return false;};for (int i = 0; i < iMaskCount; i++) {if (vis[i]) { continue; }if (DFS(i,-1)) { return true; }}return false;}};

单元测试

vector<vector<char>> grid;TEST_METHOD(TestMethod11){grid = { {'a','a','a','a'},{'a','b','b','a'},{'a','b','b','a'},{'a','a','a','a'} };auto res = Solution().containsCycle(grid);AssertEx(true, res);}TEST_METHOD(TestMethod12){grid = { {'c','c','c','a'},{'c','d','c','c'},{'c','c','e','c'},{'f','c','c','c'} };auto res = Solution().containsCycle(grid);AssertEx(true, res);}TEST_METHOD(TestMethod13){grid = { {'a','b','b'},{'b','z','b'},{'b','b','a'} };auto res = Solution().containsCycle(grid);AssertEx(false, res);}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。