LeetCode 题解工作台
检查网格中是否存在有效路径
给你一个 m x n 的网格 grid 。网格里的每个单元都代表一条街道。 grid[i][j] 的街道可以是： 1 表示连接左单元格和右单元格的街道。 2 表示连接上单元格和下单元格的街道。 3 表示连接左单元格和下单元格的街道。 4 表示连接右单元格和下单元格的街道。 5 表示连接左单元格和上单…
5
题型
4
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
class Solution: def hasValidPath(self, grid: List[List[int]]) -> bool:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：
- 1 表示连接左单元格和右单元格的街道。
- 2 表示连接上单元格和下单元格的街道。
- 3 表示连接左单元格和下单元格的街道。
- 4 表示连接右单元格和下单元格的街道。
- 5 表示连接左单元格和上单元格的街道。
- 6 表示连接右单元格和上单元格的街道。
你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。
注意：你 不能 变更街道。
如果网格中存在有效的路径，则返回 true，否则返回 false 。
示例 1：
输入：grid = [[2,4,3],[6,5,2]] 输出：true 解释：如图所示，你可以从 (0, 0) 开始，访问网格中的所有单元格并到达 (m - 1, n - 1) 。
示例 2：
输入：grid = [[1,2,1],[1,2,1]] 输出：false 解释：如图所示，单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连，你只会停在 (0, 0) 处。
示例 3：
输入：grid = [[1,1,2]] 输出：false 解释：你会停在 (0, 1)，而且无法到达 (0, 2) 。
示例 4：
输入：grid = [[1,1,1,1,1,1,3]] 输出：true
示例 5：
输入：grid = [[2],[2],[2],[2],[2],[2],[6]] 输出：true
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 3001 <= grid[i][j] <= 6
解题思路
方法一
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)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for correct implementation of DFS or BFS to explore the grid.
- question_mark
Pay attention to how the candidate handles edge cases like unreachable cells or circular paths.
- question_mark
Check if the candidate optimizes their algorithm to avoid unnecessary exploration of already visited cells.
常见陷阱
外企场景- error
Forgetting to mark visited cells, leading to infinite loops or revisiting cells unnecessarily.
- error
Not correctly managing the street connection rules, resulting in invalid moves and incorrect results.
- error
Overcomplicating the solution by not simplifying the pathfinding logic.
进阶变体
外企场景- arrow_right_alt
Increase grid size to test scalability with larger m and n values.
- arrow_right_alt
Introduce more complex street connection rules and validate the pathfinding ability.
- arrow_right_alt
Modify the grid to have isolated regions, testing how the algorithm handles disconnected paths.