题目描述
思路解析动画文字版
记牢这一句:撞上一个同字母、不是来处、又已经访问过的格子,就是环。下面从左上角 (0,0) 开始,顺着外圈的 a 一步步走,看这股搜索最后怎么绕回起点附近、把环兜住。
舞台 · 4 乘 4 字母网格：舞台是一个 4 行 4 列的字母网格,外圈一整圈是字母 a,正中间 2 乘 2 是字母 b。我们要找的是:同一个字母能不能围成一条首尾相接、长度至少为 4 的环。规矩是一格一格走,只在相同字母之间挪动,而且不能马上退回上一步来的那格。盯着外圈这圈 a,它很可能就藏着一个环。
起点 (0,0) · 标记已访问：从左上角 (0,0) 开始,它是 a、还没访问过,就以它为起点发起一次搜索,先把 (0,0) 标记成已访问。约定好规矩:只往上下左右走,目标格必须和当前格同字母,同时记住自己从哪一格来,等会儿靠它排掉假环。已访问 1 个。
(0,0) 朝上 · 出界：先看 (0,0) 的上方,那里已经出了网格边界,外面没有格子,这个方向直接跳过。出界的方向不参与判断。
走入 (0,1) · 标记入栈：看 (0,0) 右边的 (0,1),它是 a、和起点同字母又没访问过,踏进去,把它标记成已访问、压进待探索栈。已访问 2 个。
走入 (1,0) · 标记入栈：再看 (0,0) 下方的 (1,0),同样是 a、没访问过,也踏进去标记入栈。此刻栈里排着 (0,1) 和 (1,0) 两个待探索的格子。已访问 3 个。
(1,0) 朝上 · 是来处,跳过：弹出栈顶的 (1,0) 来扩展,它是从 (0,0) 下来的。看它上方正好是 (0,0),那就是刚刚来的那格、是上一步的来处,绝不能算成环,跳过这个方向。这条排除来处的规矩,正是用来挡掉走一步又退回去的长度 2 假环。
(1,0) 朝右 · 字母 b,不同：(1,0) 的右边是 (1,1),它是字母 b,和我们正在追的 a 不是同一个字母,走不过去,跳过。只在相同字母之间挪动。
走入 (2,0) · 标记入栈：深度优先先弹出栈顶的 (1,0) 来扩展。它下方的 (2,0) 是 a、没访问过,踏进去标记入栈,顺着左边这一列继续往下探。已访问 4 个。
(2,0) 朝上 · 是来处,跳过：轮到 (2,0) 扩展,它从 (1,0) 来。上方是 (1,0),又是来处,同样跳过。每到一格都先把来处这条路排掉,免得把回头路误当环。
(2,0) 朝右 · 字母 b,不同：(2,0) 的右边是 (2,1),它是字母 b,和我们正在追的 a 不是同一个字母,走不过去,跳过。只在相同字母之间挪动。
走入 (3,0) · 标记入栈：从 (2,0) 往下走到 (3,0),它是 a、没访问过,踏进去标记。已访问 5 个,到了左下角,准备拐上底边。
走入 (3,1) · 标记入栈：在 (3,0),上方是来处、下边和左边都出界,只剩右边的 (3,1),它是 a、没访问过,踏进去标记。已访问 6 个,沿底边往右推进。
走入 (3,2) · 标记入栈：从 (3,1) 继续往右是 (3,2),a、没访问过,踏进去。已访问 7 个。
走入 (3,3) · 标记入栈：从 (3,2) 往右走到 (3,3),a、没访问过,踏进去标记,这是右下角。已访问 8 个,接下来沿右列往上爬。
走入 (2,3) · 标记入栈：在 (3,3),右边下边都出界,往上看 (2,3),是 a、没访问过,踏进去。已访问 9 个。
走入 (1,3) · 标记入栈：从 (2,3) 往上是 (1,3),a、没访问过,踏进去标记。已访问 10 个,快爬到右上角了。
走入 (0,3) · 标记入栈：从 (1,3) 往上走到 (0,3),a、没访问过,踏进去。已访问 11 个,到了右上角。
走入 (0,2) · 标记入栈：在 (0,3),上边右边都出界,往左看 (0,2),是 a、没访问过,踏进去标记。已访问 12 个,十二个 a 已连成一长串,只差最后一步合龙。
(0,2) 朝右 · 是来处,跳过：扩展 (0,2)。先看它右边的 (0,3),那正是我们刚从那儿过来的来处,按规矩跳过,这一步不能算环。
(0,2) 朝下 · 字母 b,不同：(0,2) 的下边是 (1,2),它是字母 b,和我们正在追的 a 不是同一个字母,走不过去,跳过。只在相同字母之间挪动。
撞上已访问的 (0,1) · 有环,返回 true：关键一步:看 (0,2) 左边的 (0,1)。它是 a、和当前格同字母,又不是我们的来处,可它早就被访问过了,正是最开始从 (0,0) 标记的那个 (0,1)。绕了外圈一整圈又撞回这个老格子,说明这串 a 首尾接上了,存在一个环,返回 true。
回放 · 外圈 a 闭合成环：回看全程:从 (0,0) 出发,顺着外圈的 a 一路标记,先沿左列下到 (3,0),再转底边、上右列、过顶边,最后 (0,2) 撞上早已访问的 (0,1),环就此闭合。判定一个环始终只看那一句话:走到一个同字母、又不是上一步来处、却已经访问过的格子。答案 true。
边界想清:单格围不成环返回 false、2 乘 2 全同字母是最小环返回 true、相邻都不同字母直接 false。
面试重点:判环要同字母加非来处加已访问三条齐全、深广优先与并查集思路殊途同归、时间空间都是 O(m 乘 n)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution:
def containsCycle(self, grid: List[List[str]]) -> bool:
m, n = len(grid), len(grid[0])
vis = [[False] * n for _ in range(m)]
dirs = (-1, 0, 1, 0, -1)
for i, row in enumerate(grid):
for j, x in enumerate(row):
if vis[i][j]:
continue
vis[i][j] = True
q = [(i, j, -1, -1)]
while q:
x, y, px, py = q.pop()
for dx, dy in pairwise(dirs):
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n:
if grid[nx][ny] != grid[i][j] or (nx == px and ny == py):
continue
if vis[nx][ny]:
return True
vis[nx][ny] = True
q.append((nx, ny, x, y))
return False复杂度
- 时间：O(m·n)，m 行 n 列共 m 乘 n 个格子。靠一张全局 vis,每个格子最多被某次搜索访问一次、外层再扫一次,每格只看四个固定方向,都是常数操作。整体随格子总数线性增长
- 空间：O(m·n)，按峰值算。vis 已访问表是 m 乘 n;深度优先的栈或广度优先的队列,最坏要排到接近一整块的格子,也是 m 乘 n 量级。峰值就是 O(m·n),不随面积平方增长
易错点
面试追问把动画讲成自己的话
追问判定有环的那一条到底是什么,能不能只看已访问?
追问这题用深度或广度优先,和用并查集有什么区别?
追问为什么时间能做到线性,空间又是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
给定行和列的和求可行矩阵
LeetCode 1605 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题