我们需要解决两个关键问题：
- 站在 $(x,y)$，下一步可以往哪些方向移动？
- 如何判断相邻街道是否连通？示例 2 的街道不是连通的，无法移动。
对于第一个问题，我们可以创建一个方向向量数组，保存每种街道的移动方向。例如：
- 站在街道 1，我们可以往左或者往右移动，对应的方向向量分别为 $(0,-1)$ 和 $(0,1)$。
- 站在街道 3，我们可以往左或者往下移动，对应的方向向量分别为 $(0,-1)$ 和 $(1,0)$。
对于第二个问题，如果两条相邻街道可以互相到达，那么这两条街道就是连通的。
- 如果街道 1 的右边是街道 3，我们可以从街道 1 往右移动到街道 3，也可以从街道 3 往左移动到街道 1。
- 如果要从街道 1 往右移动，那么只要右边相邻街道能往左移动就行，也就是包含往左的方向向量 $(0,-1)$。
- 一般地，如果从当前位置往 $(\textit{dx},\textit{dy})$ 方向移动到相邻街道，那么相邻街道必须包含相反的方向向量 $(-\textit{dx},-\textit{dy})$。
###py
DIRS = (
(),
((0, -1), (0, 1)), # 站在街道 1，可以往左或者往右
((-1, 0), (1, 0)), # 站在街道 2，可以往上或者往下
((0, -1), (1, 0)), # 站在街道 3，可以往左或者往下
((0, 1), (1, 0)), # 站在街道 4，可以往右或者往下
((0, -1), (-1, 0)), # 站在街道 5，可以往左或者往上
((0, 1), (-1, 0)), # 站在街道 6，可以往右或者往上
)
class Solution:
def hasValidPath(self, grid: list[list[int]]) -> bool:
m, n = len(grid), len(grid[0])
vis = [[False] * n for _ in range(m)]
def dfs(x: int, y: int) -> bool:
if x == m - 1 and y == n - 1:
return True
vis[x][y] = True # 标记 (x, y) 访问过，从而避免重复访问
for dx, dy in DIRS[grid[x][y]]: # 枚举下一步往哪走
i, j = x + dx, y + dy
if 0 <= i < m and 0 <= j < n and not vis[i][j] and \
(-dx, -dy) in DIRS[grid[i][j]] and dfs(i, j):
return True
return False
return dfs(0, 0)
###java
class Solution {
private static final int[][][] DIRS = {
{},
{{0, -1}, {0, 1}}, // 站在街道 1，可以往左或者往右
{{-1, 0}, {1, 0}}, // 站在街道 2，可以往上或者往下
{{0, -1}, {1, 0}}, // 站在街道 3，可以往左或者往下
{{0, 1}, {1, 0}}, // 站在街道 4，可以往右或者往下
{{0, -1}, {-1, 0}}, // 站在街道 5，可以往左或者往上
{{0, 1}, {-1, 0}}, // 站在街道 6，可以往右或者往上
};
public boolean hasValidPath(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
boolean[][] vis = new boolean[m][n];
return dfs(0, 0, grid, vis);
}
private boolean dfs(int x, int y, int[][] grid, boolean[][] vis) {
int m = grid.length;
int n = grid[x].length;
if (x == m - 1 && y == n - 1) {
return true;
}
vis[x][y] = true; // 标记 (x, y) 访问过，从而避免重复访问
for (int[] d : DIRS[grid[x][y]]) { // 枚举下一步往哪走
int i = x + d[0];
int j = y + d[1];
if (0 <= i && i < m && 0 <= j && j < n && !vis[i][j] &&
contains(grid[i][j], -d[0], -d[1]) && dfs(i, j, grid, vis)) {
return true;
}
}
return false;
}
// 判断街道 street 是否包含移动方向 (dx, dy)
private boolean contains(int street, int dx, int dy) {
int[][] ds = DIRS[street];
return ds[0][0] == dx && ds[0][1] == dy ||
ds[1][0] == dx && ds[1][1] == dy;
}
}
###cpp
class Solution {
static constexpr int DIRS[7][2][2] = {
{},
{{0, -1}, {0, 1}}, // 站在街道 1，可以往左或者往右
{{-1, 0}, {1, 0}}, // 站在街道 2，可以往上或者往下
{{0, -1}, {1, 0}}, // 站在街道 3，可以往左或者往下
{{0, 1}, {1, 0}}, // 站在街道 4，可以往右或者往下
{{0, -1}, {-1, 0}}, // 站在街道 5，可以往左或者往上
{{0, 1}, {-1, 0}}, // 站在街道 6，可以往右或者往上
};
// 判断街道 street 是否包含移动方向 (dx, dy)
bool contains(int street, int dx, int dy) {
auto& ds = DIRS[street];
return ds[0][0] == dx && ds[0][1] == dy ||
ds[1][0] == dx && ds[1][1] == dy;
}
public:
bool hasValidPath(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector vis(m, vector<int8_t>(n));
auto dfs = [&](this auto&& dfs, int x, int y) -> bool {
if (x == m - 1 && y == n - 1) {
return true;
}
vis[x][y] = true; // 标记 (x, y) 访问过，从而避免重复访问
for (auto& [dx, dy] : DIRS[grid[x][y]]) { // 枚举下一步往哪走
int i = x + dx, j = y + dy;
if (0 <= i && i < m && 0 <= j && j < n && !vis[i][j] &&
contains(grid[i][j], -dx, -dy) && dfs(i, j)) {
return true;
}
}
return false;
};
return dfs(0, 0);
}
};
###c
static const int DIRS[7][2][2] = {
{},
{{0, -1}, {0, 1}}, // 站在街道 1，可以往左或者往右
{{-1, 0}, {1, 0}}, // 站在街道 2，可以往上或者往下
{{0, -1}, {1, 0}}, // 站在街道 3，可以往左或者往下
{{0, 1}, {1, 0}}, // 站在街道 4，可以往右或者往下
{{0, -1}, {-1, 0}}, // 站在街道 5，可以往左或者往上
{{0, 1}, {-1, 0}}, // 站在街道 6，可以往右或者往上
};
// 判断街道 street 是否包含移动方向 (dx, dy)
bool contains(int street, int dx, int dy) {
return DIRS[street][0][0] == dx && DIRS[street][0][1] == dy ||
DIRS[street][1][0] == dx && DIRS[street][1][1] == dy;
}
bool hasValidPath(int** grid, int gridSize, int* gridColSize) {
int m = gridSize, n = gridColSize[0];
bool** vis = malloc(m * sizeof(bool*));
for (int i = 0; i < m; i++) {
vis[i] = calloc(n, sizeof(bool));
}
bool dfs(int x, int y) {
if (x == m - 1 && y == n - 1) {
return true;
}
vis[x][y] = true; // 标记 (x, y) 访问过，从而避免重复访问
for (int k = 0; k < 2; k++) { // 枚举下一步往哪走
int* dir = DIRS[grid[x][y]][k];
int i = x + dir[0], j = y + dir[1];
if (0 <= i && i < m && 0 <= j && j < n && !vis[i][j] &&
contains(grid[i][j], -dir[0], -dir[1]) && dfs(i, j)) {
return true;
}
}
return false;
}
bool ans = dfs(0, 0);
for (int i = 0; i < m; i++) {
free(vis[i]);
}
free(vis);
return ans;
}
###go
var dirs = [7][2][2]int{
{},
{{0, -1}, {0, 1}}, // 站在街道 1，可以往左或者往右
{{-1, 0}, {1, 0}}, // 站在街道 2，可以往上或者往下
{{0, -1}, {1, 0}}, // 站在街道 3，可以往左或者往下
{{0, 1}, {1, 0}}, // 站在街道 4，可以往右或者往下
{{0, -1}, {-1, 0}}, // 站在街道 5，可以往左或者往上
{{0, 1}, {-1, 0}}, // 站在街道 6，可以往右或者往上
}
// 判断街道 street 是否包含移动方向 dir
func contains(street int, dir [2]int) bool {
// 也可以写 slices.Contains(dirs[street][:], dir)
return dirs[street][0] == dir || dirs[street][1] == dir
}
func hasValidPath(grid [][]int) bool {
m, n := len(grid), len(grid[0])
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
var dfs func(int, int) bool
dfs = func(x, y int) bool {
if x == m-1 && y == n-1 {
return true
}
vis[x][y] = true // 标记 (x, y) 访问过，从而避免重复访问
for _, d := range dirs[grid[x][y]] { // 枚举下一步往哪走
i, j := x+d[0], y+d[1]
if 0 <= i && i < m && 0 <= j && j < n && !vis[i][j] &&
contains(grid[i][j], [2]int{-d[0], -d[1]}) && dfs(i, j) {
return true
}
}
return false
}
return dfs(0, 0)
}
###js
const DIRS = [
[],
[[0, -1], [0, 1]], // 站在街道 1，可以往左或者往右
[[-1, 0], [1, 0]], // 站在街道 2，可以往上或者往下
[[0, -1], [1, 0]], // 站在街道 3，可以往左或者往下
[[0, 1], [1, 0]], // 站在街道 4，可以往右或者往下
[[0, -1], [-1, 0]], // 站在街道 5，可以往左或者往上
[[0, 1], [-1, 0]], // 站在街道 6，可以往右或者往上
];
// 判断街道 street 是否包含移动方向 (dx, dy)
function contains(street, dx, dy) {
const ds = DIRS[street];
return ds[0][0] === dx && ds[0][1] === dy ||
ds[1][0] === dx && ds[1][1] === dy;
}
var hasValidPath = function(grid) {
const m = grid.length, n = grid[0].length;
const vis = Array.from({ length: m }, () => Array(n).fill(false));
function dfs(x, y) {
if (x === m - 1 && y === n - 1) {
return true;
}
vis[x][y] = true; // 标记 (x, y) 访问过，从而避免重复访问
for (const [dx, dy] of DIRS[grid[x][y]]) { // 枚举下一步往哪走
const i = x + dx, j = y + dy;
if (0 <= i && i < m && 0 <= j && j < n && !vis[i][j] &&
contains(grid[i][j], -dx, -dy) && dfs(i, j)) {
return true;
}
}
return false;
}
return dfs(0, 0);
};
###rust
impl Solution {
const DIRS: [[(i32, i32); 2]; 7] = [
[(0, 0), (0, 0)],
[(0, -1), (0, 1)], // 站在街道 1，可以往左或者往右
[(-1, 0), (1, 0)], // 站在街道 2，可以往上或者往下
[(0, -1), (1, 0)], // 站在街道 3，可以往左或者往下
[(0, 1), (1, 0)], // 站在街道 4，可以往右或者往下
[(0, -1), (-1, 0)], // 站在街道 5，可以往左或者往上
[(0, 1), (-1, 0)], // 站在街道 6，可以往右或者往上
];
// 判断街道 street 是否包含移动方向 dir
fn contains(street: i32, dir: (i32, i32)) -> bool {
let ds = Self::DIRS[street as usize];
ds[0] == dir || ds[1] == dir
}
pub fn has_valid_path(grid: Vec<Vec<i32>>) -> bool {
fn dfs(x: usize, y: usize, grid: &[Vec<i32>], vis: &mut [Vec<bool>]) -> bool {
let m = grid.len();
let n = grid[x].len();
if x == m - 1 && y == n - 1 {
return true;
}
vis[x][y] = true; // 标记 (x, y) 访问过，从而避免重复访问
for &(dx, dy) in Solution::DIRS[grid[x][y] as usize].iter() { // 枚举下一步往哪走
let i = x + dx as usize;
let j = y + dy as usize;
if i < m && j < n && !vis[i][j] &&
Solution::contains(grid[i][j], (-dx, -dy)) && dfs(i, j, grid, vis) {
return true;
}
}
false
}
let m = grid.len();
let n = grid[0].len();
let mut vis = vec![vec![false; n]; m];
dfs(0, 0, &grid, &mut vis)
}
}
复杂度分析
- 时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别是 $\textit{grid}$ 的行数和列数。
- 空间复杂度：$\mathcal{O}(mn)$。
专题训练
见下面网格图题单的「一、网格图 DFS」。
分类题单
如何科学刷题？
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
我的题解精选（已分类）
欢迎关注 B站@灵茶山艾府
登录
