1559. 二维网格图中探测环

ITCharge大约 4 分钟

---

1559. 二维网格图中探测环

标签：深度优先搜索、广度优先搜索、并查集、数组、矩阵
难度：中等

题目链接

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

题目大意

描述：给定一个二维字符网格 $grid$ ，大小 $m \times n$ 。每个单元格包含小写字母。

要求：判断网格中是否存在由相同字符组成的环。环定义为长度 $\ge 4$ 的循环路径，路径上的单元格字符相同，且每个单元格只能经过一次，相邻单元格四联通。

说明：

$1 \le m, n \le 500$ 。
$grid[i][j]$ 为小写字母。

示例：

示例 1：

输入：grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
输出：true
解释：如下图所示，有 2 个用不同颜色标出来的环：
![](https://assets.leetcode.cn/aliyun-lc-upload/uploads/2020/08/22/5482e11.png)

示例 2：

输入：grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
输出：true
解释：如下图所示，只有高亮所示的一个合法环：
![](https://assets.leetcode.cn/aliyun-lc-upload/uploads/2020/08/22/5482e22.png)

解题思路

思路 1：DFS + 父节点标记

1. 核心思想

在无向图中检测环的方式：DFS 遍历时，如果遇到已访问的邻居节点，且该节点不是当前节点的父节点，则说明存在环。

这里将二维网格视为无向图，每个单元格与上下左右的相同字符单元格相连。

2. 具体步骤

第 1 步：创建 $visited$ 数组记录访问状态。

第 2 步：遍历所有单元格，对未访问的单元格启动 DFS。

第 3 步：DFS 函数 $dfs(x, y, px, py, ch)$ ：

参数 $(x, y)$ 当前坐标， $(px, py)$ 父节点坐标， $ch$ 当前字符。
标记 $(x, y)$ 已访问。
遍历四个方向 $(nx, ny)$ $(n x, n y)$ ：
- 边界检查，字符必须匹配。
- 如果 $(nx, ny) == (px, py)$ ，跳过（父节点）。
- 如果已访问 → 找到环，返回 True。
- 否则递归 $dfs(nx, ny, x, y, ch)$ 。

第 4 步：任一 DFS 返回 True 则整体返回 True。

3. 正确性证明

无向图 DFS 中，遇到已访问节点且不是父节点，说明存在一条从该节点出发、经不同路径回到自身的回路。
由于网格中的边只在相同字符之间，环上的所有字符必然相同。
环长度 $\ge 4$ 由网格结构保证（最小环为 $2 \times 2$ 的 $4$ 个格子）。

4. 举例说明

以 $grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]$ 为例：

a a a a
a b b a
a b b a
a a a a

外围的 a 构成一个环（ $4 \times 4$ 的外框），中间的 b 也构成一个环（ $2 \times 2$ ）。返回 True。

以 $grid = [["a","a"],["a","a"]]$ 为例：

a a
a a

四个 a 组成一个 $2 \times 2$ 的环，返回 True。

思路 1：代码

class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(x, y, px, py, ch):
            visited[x][y] = True
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if nx < 0 or nx >= m or ny < 0 or ny >= n:
                    continue
                if grid[nx][ny] != ch:
                    continue
                if nx == px and ny == py:
                    continue
                if visited[nx][ny]:
                    return True
                if dfs(nx, ny, x, y, ch):
                    return True
            return False

        for i in range(m):
            for j in range(n):
                if not visited[i][j]:
                    if dfs(i, j, -1, -1, grid[i][j]):
                        return True
        return False

思路 1：复杂度分析

时间复杂度： $O(m \times n)$ ，每个单元格访问一次。
空间复杂度： $O(m \times n)$ ，visited 数组和递归栈空间。

思路 2：并查集

1. 核心思想

将网格视为图，每条边连接相邻的相同字符单元格。如果添加一条边时，两个端点已经在同一集合中，则说明形成了环。

遍历每个单元格 $(i, j)$ ，只检查右侧和下边的相邻单元格（避免重复加边）。如果字符相同且已连通，则有环。

class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        m, n = len(grid), len(grid[0])
        parent = list(range(m * n))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(x, y):
            rx, ry = find(x), find(y)
            if rx == ry:
                return False  # 已连通，说明有环
            parent[ry] = rx
            return True

        for i in range(m):
            for j in range(n):
                idx = i * n + j
                # 检查右侧
                if j + 1 < n and grid[i][j] == grid[i][j + 1]:
                    if not union(idx, idx + 1):
                        return True
                # 检查下侧
                if i + 1 < m and grid[i][j] == grid[i + 1][j]:
                    if not union(idx, idx + n):
                        return True
        return False

思路 2：复杂度分析

时间复杂度： $O(m \times n \times \alpha(m \times n))$ ，近似线性。
空间复杂度： $O(m \times n)$ ，并查集。