题目描述
思路解析动画文字版
记牢这句话:相邻两格,双向敞口才连通。下面从左上角开始做 BFS,每次只把和当前格互相敞口的邻居收进队列,看这股「水」最后能不能漫到右下角。先把编号和方向对上号:1 是左右,2 是上下,3 是左下,4 是右下,5 是左上,6 是右上。
BFS 起步 · 从左上角 (0,0)：舞台是 2 行 3 列的网格,格子里是街道编号。起点 (0,0) 编号 2,先把它放进队列、标成已可达。终点是右下角 (1,2)。BFS 的规矩是:每次从队列里取一个格子,看它两个敞口方向上的邻居,谁和它互相敞口、又还没来过,就把谁收进队列。开始扩散。
取出 (0,0) · 编号 2(上下)：从队列取出 (0,0),它的编号是 2,朝上下两个方向开口。挨个看这两个方向上的邻居,判断能不能接上。
(0,0) 朝上 · 出界：(0,0) 朝上有开口,可是上边已经到网格外了,没有格子,这个方向跳过。
查看 (1,0) · 编号 6(右上)：(0,0) 朝下开口,看下边的 (1,0),它是编号 6(右上)。要连通,它得朝上回敞口才行,查一下编号 6 朝不朝上。
连通 (0,0) 和 (1,0) · 入队：(1,0) 编号 6 正好朝上开口,双方互相敞口,接上了。把 (1,0) 标成已可达、放进队列,等会儿轮到它再往外扩。已确认可达 2 个格子。
取出 (1,0) · 编号 6(右上)：从队列取出 (1,0),它的编号是 6,朝右上两个方向开口。挨个看这两个方向上的邻居,判断能不能接上。
查看 (1,1) · 编号 5(左上)：(1,0) 朝右开口,看右边的 (1,1),它是编号 5(左上)。要连通,它得朝左回敞口才行,查一下编号 5 朝不朝左。
连通 (1,0) 和 (1,1) · 入队：(1,1) 编号 5 正好朝左开口,双方互相敞口,接上了。把 (1,1) 标成已可达、放进队列,等会儿轮到它再往外扩。已确认可达 3 个格子。
查看 (0,0) · 已可达,跳过：(1,0) 朝上边看 (0,0),它编号 2 也朝下开口,本来是连通的,但它早就在已可达里了,不用重复收,跳过。
取出 (1,1) · 编号 5(左上)：从队列取出 (1,1),它的编号是 5,朝左上两个方向开口。挨个看这两个方向上的邻居,判断能不能接上。
查看 (1,0) · 已可达,跳过：(1,1) 朝左边看 (1,0),它编号 6 也朝右开口,本来是连通的,但它早就在已可达里了,不用重复收,跳过。
查看 (0,1) · 编号 4(右下)：(1,1) 朝上开口,看上边的 (0,1),它是编号 4(右下)。要连通,它得朝下回敞口才行,查一下编号 4 朝不朝下。
连通 (1,1) 和 (0,1) · 入队：(0,1) 编号 4 正好朝下开口,双方互相敞口,接上了。把 (0,1) 标成已可达、放进队列,等会儿轮到它再往外扩。已确认可达 4 个格子。
取出 (0,1) · 编号 4(右下)：从队列取出 (0,1),它的编号是 4,朝右下两个方向开口。挨个看这两个方向上的邻居,判断能不能接上。
查看 (0,2) · 编号 3(左下)：(0,1) 朝右开口,看右边的 (0,2),它是编号 3(左下)。要连通,它得朝左回敞口才行,查一下编号 3 朝不朝左。
连通 (0,1) 和 (0,2) · 入队：(0,2) 编号 3 正好朝左开口,双方互相敞口,接上了。把 (0,2) 标成已可达、放进队列,等会儿轮到它再往外扩。已确认可达 5 个格子。
查看 (1,1) · 已可达,跳过：(0,1) 朝下边看 (1,1),它编号 5 也朝上开口,本来是连通的,但它早就在已可达里了,不用重复收,跳过。
取出 (0,2) · 编号 3(左下)：从队列取出 (0,2),它的编号是 3,朝左下两个方向开口。挨个看这两个方向上的邻居,判断能不能接上。
查看 (0,1) · 已可达,跳过：(0,2) 朝左边看 (0,1),它编号 4 也朝右开口,本来是连通的,但它早就在已可达里了,不用重复收,跳过。
查看 (1,2) · 编号 2(上下)：(0,2) 朝下开口,看下边的 (1,2),它是编号 2(上下)。要连通,它得朝上回敞口才行,查一下编号 2 朝不朝上。
连通 (0,2) 和 (1,2) · 入队：(1,2) 编号 2 正好朝上开口,双方互相敞口,接上了。把 (1,2) 标成已可达、放进队列,等会儿轮到它再往外扩。已确认可达 6 个格子。
取出 (1,2) · 编号 2(上下)：从队列取出 (1,2),它的编号是 2,朝上下两个方向开口。挨个看这两个方向上的邻居,判断能不能接上。
查看 (0,2) · 已可达,跳过：(1,2) 朝上边看 (0,2),它编号 3 也朝下开口,本来是连通的,但它早就在已可达里了,不用重复收,跳过。
(1,2) 朝下 · 出界：(1,2) 朝下有开口,可是下边已经到网格外了,没有格子,这个方向跳过。
终点 (1,2) 可达 · 答案 true：队列空了,BFS 结束。六个格子全被收进了已可达,右下角终点 (1,2) 当然也在里面。从左上角顺着街道确实能走到右下角,存在有效路径,返回 true。回看全程,无非就是:相邻互相敞口才连通,从起点 BFS 扩散,看终点收没收进来。
边界想清:单格起点即终点直接成立、走到一半被不敞口的格子截断就 false、一整列上下贯通且末段朝上接住就 true。
面试重点:双向敞口才连通、静态判连通并查集最省心而要路线用 BFS 或 DFS、路径压缩把 find 摊还压到近常数。
参考代码
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 hasValidPath(self, grid: List[List[int]]) -> bool: m, n = len(grid), len(grid[0]) p = list(range(m * n)) def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def left(i, j): if j > 0 and grid[i][j - 1] in (1, 4, 6): p[find(i * n + j)] = find(i * n + j - 1) def right(i, j): if j < n - 1 and grid[i][j + 1] in (1, 3, 5): p[find(i * n + j)] = find(i * n + j + 1) def up(i, j): if i > 0 and grid[i - 1][j] in (2, 3, 4): p[find(i * n + j)] = find((i - 1) * n + j) def down(i, j): if i < m - 1 and grid[i + 1][j] in (2, 5, 6): p[find(i * n + j)] = find((i + 1) * n + j) for i in range(m): for j in range(n): e = grid[i][j] if e == 1: left(i, j) right(i, j) elif e == 2: up(i, j) down(i, j) elif e == 3: left(i, j) down(i, j) elif e == 4: right(i, j) down(i, j) elif e == 5: left(i, j) up(i, j) else: right(i, j) up(i, j) return find(0) == find(m * n - 1)复杂度
- 时间：O(m·n)，m 是行数,n 是列数,一共 m 乘 n 个格子。BFS 每个格子进出队列各一次,每次只看它两个固定方向的邻居,常数次操作;并查集写法扫每个格子做常数次合并,带路径压缩的 find 摊还几乎是常数。整体随格子总数线性增长,是 O(m·n)
- 空间：O(m·n)，按峰值算。BFS 要一个已可达标记(m 乘 n 个格子)加一个队列,最坏要装下接近全部格子;并查集要一个长度 m 乘 n 的父数组。两种写法峰值都是 O(m·n),不随面积平方增长
易错点
面试追问把动画讲成自己的话
追问为什么必须双向敞口才算连通,只验一边行不行?
追问这题用并查集和用 BFS 或 DFS,该怎么选?
追问并查集里的路径压缩起什么作用?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
重新规划路线
LeetCode 1466 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题