LeetCode 1391中等图 · 网格
检查网格中是否存在有效路径 图解题解
这道题到底在问什么
给你一个 m 行 n 列的网格 grid,grid 里每个格子是一段街道:1 连左右,2 连上下,3 连左下,4 连右下,5 连左上,6 连右上。从左上角 (0,0) 出发,只能沿街道走,问是否存在一条有效路径到右下角 (m-1,n-1)。注意你不能旋转任何一段街道。
- 输入
- grid=[[2,4,3],[6,5,2]]
- 输出
- true
- 输入
- grid=[[1,2,1],[1,2,1]]
- 输出
- false
先想最直接的笨办法
从队列取出 (0,0),它的编号是 2,朝上下两个方向开口。挨个看这两个方向上的邻居,判断能不能接上。（动画第 5 步）
最优解：一步一步想明白
- 3记牢这句话:相邻两格,双向敞口才连通。下面从左上角开始做 BFS,每次只把和当前格互相敞口的邻居收进队列,看这股「水」最后能不能漫到右下角。先把编号和方向对上号:1 是左右,2 是上下,3 是左下,4 是右下,5 是左上,6 是右上。
- 4起点入队,目标 (1,2)舞台是 2 行 3 列的网格,格子里是街道编号。起点 (0,0) 编号 2,先把它放进队列、标成已可达。终点是右下角 (1,2)。BFS 的规矩是:每次从队列里取一个格子,看它两个敞口方向上的邻居,谁和它互相敞口、又还没来过,就把谁收进队列。开始扩散。
- 5当前扩展 (0,0)从队列取出 (0,0),它的编号是 2,朝上下两个方向开口。挨个看这两个方向上的邻居,判断能不能接上。
- 6上边出界(0,0) 朝上有开口,可是上边已经到网格外了,没有格子,这个方向跳过。
- 7查 (1,0) 是否朝上(0,0) 朝下开口,看下边的 (1,0),它是编号 6(右上)。要连通,它得朝上回敞口才行,查一下编号 6 朝不朝上。
- 8(1,0) 已可达(1,0) 编号 6 正好朝上开口,双方互相敞口,接上了。把 (1,0) 标成已可达、放进队列,等会儿轮到它再往外扩。已确认可达 2 个格子。
- 9当前扩展 (1,0)从队列取出 (1,0),它的编号是 6,朝右上两个方向开口。挨个看这两个方向上的邻居,判断能不能接上。
- 10查 (1,1) 是否朝左(1,0) 朝右开口,看右边的 (1,1),它是编号 5(左上)。要连通,它得朝左回敞口才行,查一下编号 5 朝不朝左。
- 11(1,1) 已可达(1,1) 编号 5 正好朝左开口,双方互相敞口,接上了。把 (1,1) 标成已可达、放进队列,等会儿轮到它再往外扩。已确认可达 3 个格子。
- 12(0,0) 之前已收(1,0) 朝上边看 (0,0),它编号 2 也朝下开口,本来是连通的,但它早就在已可达里了,不用重复收,跳过。
- 13当前扩展 (1,1)从队列取出 (1,1),它的编号是 5,朝左上两个方向开口。挨个看这两个方向上的邻居,判断能不能接上。
- 14(1,0) 之前已收(1,1) 朝左边看 (1,0),它编号 6 也朝右开口,本来是连通的,但它早就在已可达里了,不用重复收,跳过。
- 15查 (0,1) 是否朝下(1,1) 朝上开口,看上边的 (0,1),它是编号 4(右下)。要连通,它得朝下回敞口才行,查一下编号 4 朝不朝下。
- 16(0,1) 已可达(0,1) 编号 4 正好朝下开口,双方互相敞口,接上了。把 (0,1) 标成已可达、放进队列,等会儿轮到它再往外扩。已确认可达 4 个格子。
- 17当前扩展 (0,1)从队列取出 (0,1),它的编号是 4,朝右下两个方向开口。挨个看这两个方向上的邻居,判断能不能接上。
- 18查 (0,2) 是否朝左(0,1) 朝右开口,看右边的 (0,2),它是编号 3(左下)。要连通,它得朝左回敞口才行,查一下编号 3 朝不朝左。
- 19(0,2) 已可达(0,2) 编号 3 正好朝左开口,双方互相敞口,接上了。把 (0,2) 标成已可达、放进队列,等会儿轮到它再往外扩。已确认可达 5 个格子。
- 20(1,1) 之前已收(0,1) 朝下边看 (1,1),它编号 5 也朝上开口,本来是连通的,但它早就在已可达里了,不用重复收,跳过。
- 21当前扩展 (0,2)从队列取出 (0,2),它的编号是 3,朝左下两个方向开口。挨个看这两个方向上的邻居,判断能不能接上。
- 22(0,1) 之前已收(0,2) 朝左边看 (0,1),它编号 4 也朝右开口,本来是连通的,但它早就在已可达里了,不用重复收,跳过。
- 23查 (1,2) 是否朝上(0,2) 朝下开口,看下边的 (1,2),它是编号 2(上下)。要连通,它得朝上回敞口才行,查一下编号 2 朝不朝上。
- 24(1,2) 已可达(1,2) 编号 2 正好朝上开口,双方互相敞口,接上了。把 (1,2) 标成已可达、放进队列,等会儿轮到它再往外扩。已确认可达 6 个格子。
- 25当前扩展 (1,2)从队列取出 (1,2),它的编号是 2,朝上下两个方向开口。挨个看这两个方向上的邻居,判断能不能接上。
- 26(0,2) 之前已收(1,2) 朝上边看 (0,2),它编号 3 也朝下开口,本来是连通的,但它早就在已可达里了,不用重复收,跳过。
- 27下边出界(1,2) 朝下有开口,可是下边已经到网格外了,没有格子,这个方向跳过。
- 28已可达 6 / 6队列空了,BFS 结束。六个格子全被收进了已可达,右下角终点 (1,2) 当然也在里面。从左上角顺着街道确实能走到右下角,存在有效路径,返回 true。回看全程,无非就是:相邻互相敞口才连通,从起点 BFS 扩散,看终点收没收进来。
⚠️ 容易写错的地方
✗ 错：只看当前格朝邻居开口就判连通
✓ 对：必须双方互相敞口才连通
相邻两格,只有一边朝对方开、另一边没朝回来,照样接不上,务必两边都验
✗ 错：把编号当方向数,以为数字越大开口越多
✓ 对：6 个编号都恰好只朝两个方向开
编号 1 到 6 只是六种「连哪两边」的代号,跟大小无关,得记住每个编号对应的那一对方向
✗ 错：默认能走到右下角就只查终点格自己
✓ 对：要从起点连通性判断,不是单看终点编号
不能只盯着终点编号单独下结论,终点也得和来向格子互相敞口才连得上,关键是从起点扩散出的连通块有没有把终点囊括进去
✗ 错：把网格当普通四连通随便走
✓ 对：只能沿街道开口方向走,且双向敞口
这题不是任意上下左右都能走,被街道编号死死限制,漏了这点会把不连通当成连通
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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)C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> p;
bool hasValidPath(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
p.resize(m * n);
for (int i = 0; i < p.size(); ++i) p[i] = i;
auto left = [&](int i, int j) {
if (j > 0 && (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {
p[find(i * n + j)] = find(i * n + j - 1);
}
};
auto right = [&](int i, int j) {
if (j < n - 1 && (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {
p[find(i * n + j)] = find(i * n + j + 1);
}
};
auto up = [&](int i, int j) {
if (i > 0 && (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {
p[find(i * n + j)] = find((i - 1) * n + j);
}
};
auto down = [&](int i, int j) {
if (i < m - 1 && (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {
p[find(i * n + j)] = find((i + 1) * n + j);
}
};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int e = grid[i][j];
if (e == 1) {
left(i, j);
right(i, j);
} else if (e == 2) {
up(i, j);
down(i, j);
} else if (e == 3) {
left(i, j);
down(i, j);
} else if (e == 4) {
right(i, j);
down(i, j);
} else if (e == 5) {
left(i, j);
up(i, j);
} else {
right(i, j);
up(i, j);
}
}
}
return find(0) == find(m * n - 1);
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
};Java
import java.util.*;
class Solution {
private int[] p;
private int[][] grid;
private int m;
private int n;
public boolean hasValidPath(int[][] grid) {
this.grid = grid;
m = grid.length;
n = grid[0].length;
p = new int[m * n];
for (int i = 0; i < p.length; ++i) {
p[i] = i;
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int e = grid[i][j];
if (e == 1) {
left(i, j);
right(i, j);
} else if (e == 2) {
up(i, j);
down(i, j);
} else if (e == 3) {
left(i, j);
down(i, j);
} else if (e == 4) {
right(i, j);
down(i, j);
} else if (e == 5) {
left(i, j);
up(i, j);
} else {
right(i, j);
up(i, j);
}
}
}
return find(0) == find(m * n - 1);
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
private void left(int i, int j) {
if (j > 0 && (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {
p[find(i * n + j)] = find(i * n + j - 1);
}
}
private void right(int i, int j) {
if (j < n - 1 && (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {
p[find(i * n + j)] = find(i * n + j + 1);
}
}
private void up(int i, int j) {
if (i > 0 && (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {
p[find(i * n + j)] = find((i - 1) * n + j);
}
}
private void down(int i, int j) {
if (i < m - 1 && (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {
p[find(i * n + j)] = find((i + 1) * n + j);
}
}
}复杂度
时间
O(m·n)
m 是行数,n 是列数,一共 m 乘 n 个格子。BFS 每个格子进出队列各一次,每次只看它两个固定方向的邻居,常数次操作;并查集写法扫每个格子做常数次合并,带路径压缩的 find 摊还几乎是常数。整体随格子总数线性增长,是 O(m·n)
空间
O(m·n)
按峰值算。BFS 要一个已可达标记(m 乘 n 个格子)加一个队列,最坏要装下接近全部格子;并查集要一个长度 m 乘 n 的父数组。两种写法峰值都是 O(m·n),不随面积平方增长
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 检查网格中是否存在有效路径 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么必须双向敞口才算连通,只验一边行不行?+
不行。街道是有方向的开口,想从 A 走到 B,得 A 这格朝 B 的方向有路、同时 B 那格朝 A 的方向也有路,缺一边就等于半截墙,人过不去。只验一边会把很多其实走不通的相邻格误判成连通,答案就错了。所以每次连边都要两格各自的编号都点头才算数。
这题用并查集和用 BFS 或 DFS,该怎么选?+
两种都对、复杂度都是格子总数这个量级。并查集的好处是只关心连通性、不关心具体路线,扫一遍把所有互相敞口的相邻格合并,最后比一下起点终点的根就行,代码很短。BFS 或 DFS 则更直观,从起点扩散,过程能清楚看到水漫到哪。如果后续还要问路径本身、或者边会动态增加,BFS 与 DFS 或者带额外信息的并查集更灵活。静态判连通,并查集最省心。
并查集里的路径压缩起什么作用?+
find 在往上找根的过程中,顺手把沿途每个点的父指针直接改成根,下次再 find 这些点就一步到位。这样反复合并查询后,整棵树被压得很扁,单次 find 的摊还代价几乎是常数。对这题来说,加了路径压缩,整体时间才能稳稳控制在格子总数这个量级,不会因为树退化成链而变慢。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 检查网格中是否存在有效路径 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。