题目描述
思路解析
一句话答案：LeetCode 1391 检查网格中是否存在有效路径：每格是一段只朝两个方向开口的街道，用并查集把互相敞口的相邻格并成一堆，最后看左上角和右下角在不在同一堆，时间 O(m·n·α)。
从左上角能不能顺着街道走到右下角
给一个 m 行 n 列的网格 grid，每格写着 1 到 6 的编号，每个编号是一段只朝两个固定方向开口的街道：1 连左右，2 连上下，3 连左下，4 连右下，5 连左上，6 连右上。人从左上角 (0,0) 出发，只能顺着开口走，街道不能旋转，问能不能走到右下角 (m-1,n-1)，能就返回 true、不能返回 false。
照着街道模拟走路，麻烦在哪
想直接照着走一遍：从起点沿开口挪到邻居，再接着挪，撞墙就退回来换方向。麻烦在于判断这两格到底连不连——不是挨着就能过，得当前格朝邻居有开口、邻居也朝回来有开口，两边都敞着才算一条能过的缝。
只问起点终点连不连，用并查集
题目只问起点和右下角连不连得上，并不要求把路线画出来。「谁和谁归到一块」用并查集来管——把连通的格子并成一堆，往后查两个格子在不在同一堆几乎一步到位。把每格看成一个点，扫一遍相邻格，互相敞口就并到一起，最后看左上角和右下角在不在同一堆。
六个编号各朝哪两边，怎么两两对接
连边的规矩只有一条：相邻两格，各自朝对方的方向都有开口。先把编号按开口方向理一遍：朝左开的是 1、3、5，朝右开的是 1、4、6，朝上开的是 2、5、6，朝下开的是 2、3、4，同一个编号会落进两组，因为它本就朝两个方向开。扫到某格只看它开口的两个方向：朝右开就查右邻居在不在朝左开那组，在就并起来；朝下开就查下邻居在不在朝上开那组。左邻、上邻不必自己查——并查集连通是双向的，它们轮到自己时会朝右、朝下回查，每格只管右、下两向，不漏也不重。每格最多两次对接，一趟扫完能连的缝都并好。
拿题面这组网格把格子并成几堆
拿题面 grid=[[2,4,3],[6,5,2]] 走一遍，格子按（行，列）记。(0,0) 是 2、上下开，上面出界，下邻 (1,0) 是 6、朝上开，接上。(0,1) 是 4、右下开：右邻 (0,2) 是 3、朝左开，下邻 (1,1) 是 5、朝上开，都并上，(0,1) (0,2) (1,1) 成一堆。(0,2) 朝下的 (1,2) 是 2、朝上开，收进这堆。再看 (1,0)，它朝右的 (1,1) 朝左开，一并，(0,0) (1,0) 就和这一大堆接上，六格归一堆。最后查 (0,0) 和 (1,2) 同一堆，返回 true，起点确实通到了终点。
跑多快，单格和走不通各返回什么
外层双重循环扫 m 乘 n 个格子，每格最多两次合并，带路径压缩的查根摊还几乎是常数，时间 O(m·n·α)——α 随规模增长极慢、可当常数看；再加一个父数组记归属，空间 O(m·n)。
网格只剩一格时，左上角就是右下角，天然同堆，直接返回 true，这种起点即终点别漏判。题面例二 grid=[[1,2,1],[1,2,1]] 是另一头：起点 (0,0) 是 1、只朝左右开，左边出界，右邻 (0,1) 是 2、只朝上下开、并不朝左回敞口，(0,0) 一条能并的缝都找不到，孤零零留在那堆，终点接不进来，返回 false。这也点出最爱犯的错：当前格朝邻居开就放行、不管邻居朝没朝回来，走不通的相邻格会被误当连通。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这句话:相邻两格,双向敞口才连通。下面从左上角开始做 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题