Leetcode每日一题 —— 1559. 二维网格图中探测环
- 内容介绍
- 文章标签
- 相关推荐
1559. 二维网格图中探测环 - 力扣（LeetCode）
1559. 二维网格图中探测环 - 给你一个二维字符网格数组grid，大小为m x n，你需要检查grid中是否存在 相同值 形成的环。 一个环是一条开始和结束于同一个格子的长度 大于等于 4的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值。 同时，你也不能回到上一次移动时所在的格子。比方说，环(1, 1) -> (1, 2) -> (1, 1)是不合法的，因为从 (1, 2)移动到 (1, 1)...
思路
比较典型的无向图判环题，常用的思想有 DFS / BFS / 并查集，这里咱就用并查集来做了。
先注意题目中两个条件：
- 走回头路不算环路，也就不能往回走。
- 环路径的长度要 \ge 4 才算。其实在第 1 点条件的限制下这点是必然成立的，最小的环必须要有四个格子组成。
所以这题只需要保证不走回头路，进行判环即可。
用并查集判环，要不走回头路的话，我们在扫描网格时从上至下、从左至右，对于每个格子可以只尝试合并其右方或者下方的格子，按这样的逻辑处理必然是不会有回头路滴。
如此扫描直至某个网格与其右边或者下边的网格在同一个集合中，则满足题目要求，返回 true。
1559. 二维网格图中探测环 - 力扣（LeetCode）
1559. 二维网格图中探测环 - 给你一个二维字符网格数组grid，大小为m x n，你需要检查grid中是否存在 相同值 形成的环。 一个环是一条开始和结束于同一个格子的长度 大于等于 4的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值。 同时，你也不能回到上一次移动时所在的格子。比方说，环(1, 1) -> (1, 2) -> (1, 1)是不合法的，因为从 (1, 2)移动到 (1, 1)...
思路
比较典型的无向图判环题，常用的思想有 DFS / BFS / 并查集，这里咱就用并查集来做了。
先注意题目中两个条件：
- 走回头路不算环路，也就不能往回走。
- 环路径的长度要 \ge 4 才算。其实在第 1 点条件的限制下这点是必然成立的，最小的环必须要有四个格子组成。
所以这题只需要保证不走回头路，进行判环即可。
用并查集判环，要不走回头路的话，我们在扫描网格时从上至下、从左至右，对于每个格子可以只尝试合并其右方或者下方的格子，按这样的逻辑处理必然是不会有回头路滴。
如此扫描直至某个网格与其右边或者下边的网格在同一个集合中，则满足题目要求，返回 true。