LeetCode 题解工作台
使网格图至少有一条有效路径的最小代价
给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况： 1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1] 2 ，下一步往左走，也就是你会从 gri…
6
题型
5
代码语言
3
相关题
当前训练重点
困难 · 图·搜索
答案摘要
本题实际上也是最短路模型，只不过求解的是改变方向的最小次数。 在一个边权只有 0、1 的无向图中搜索最短路径可以使用双端队列进行 BFS。其原理是当前可以扩展到的点的权重为 0 时，将其加入队首；权重为 1 时，将其加入队尾。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：
- 1 ，下一步往右走，也就是你会从
grid[i][j]走到grid[i][j + 1] - 2 ，下一步往左走，也就是你会从
grid[i][j]走到grid[i][j - 1] - 3 ，下一步往下走，也就是你会从
grid[i][j]走到grid[i + 1][j] - 4 ，下一步往上走，也就是你会从
grid[i][j]走到grid[i - 1][j]
注意网格图中可能会有 无效数字 ，因为它们可能指向 grid 以外的区域。
一开始，你会从最左上角的格子 (0,0) 出发。我们定义一条 有效路径 为从格子 (0,0) 出发，每一步都顺着数字对应方向走，最终在最右下角的格子 (m - 1, n - 1) 结束的路径。有效路径 不需要是最短路径 。
你可以花费 cost = 1 的代价修改一个格子中的数字，但每个格子中的数字 只能修改一次 。
请你返回让网格图至少有一条有效路径的最小代价。
示例 1：
输入：grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]] 输出：3 解释：你将从点 (0, 0) 出发。 到达 (3, 3) 的路径为： (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) 花费代价 cost = 1 使方向向下 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) 花费代价 cost = 1 使方向向下 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) 花费代价 cost = 1 使方向向下 --> (3, 3) 总花费为 cost = 3.
示例 2：
输入：grid = [[1,1,3],[3,2,2],[1,1,4]] 输出：0 解释：不修改任何数字你就可以从 (0, 0) 到达 (2, 2) 。
示例 3：
输入：grid = [[1,2],[4,3]] 输出：1
示例 4：
输入：grid = [[2,2,2],[2,2,2]] 输出：3
示例 5：
输入：grid = [[4]] 输出：0
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 100
解题思路
方法一：双端队列 BFS
本题实际上也是最短路模型，只不过求解的是改变方向的最小次数。
在一个边权只有 0、1 的无向图中搜索最短路径可以使用双端队列进行 BFS。其原理是当前可以扩展到的点的权重为 0 时，将其加入队首；权重为 1 时，将其加入队尾。
如果某条边权值为 0，那么新拓展出的节点权值就和当前队首节点权值相同，显然可以作为下一次拓展的起点。
class Solution:
def minCost(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dirs = [[0, 0], [0, 1], [0, -1], [1, 0], [-1, 0]]
q = deque([(0, 0, 0)])
vis = set()
while q:
i, j, d = q.popleft()
if (i, j) in vis:
continue
vis.add((i, j))
if i == m - 1 and j == n - 1:
return d
for k in range(1, 5):
x, y = i + dirs[k][0], j + dirs[k][1]
if 0 <= x < m and 0 <= y < n:
if grid[i][j] == k:
q.appendleft((x, y, d))
else:
q.append((x, y, d + 1))
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m \cdot n) because each cell is visited at most once in BFS or Dijkstra traversal. Space complexity is O(m \cdot n) to store visited states and cumulative cost for each cell in the grid. |
| 空间 | O(n \cdot m) |
面试官常问的追问
外企场景- question_mark
Recognize the problem as a shortest path on a weighted grid using BFS.
- question_mark
Consider edge cases where arrows point outside the grid or initial path is already valid.
- question_mark
Be prepared to justify why 0-1 BFS or priority queue yields minimum modification cost.
常见陷阱
外企场景- error
Failing to correctly assign zero cost to moves following the existing arrow direction.
- error
Overlooking cells with arrows pointing outside the grid, leading to invalid path assumptions.
- error
Using standard BFS without handling edge weights, which undercounts modification costs.
进阶变体
外企场景- arrow_right_alt
Find the maximum number of valid paths from start to end instead of minimum cost.
- arrow_right_alt
Allow diagonal movements with corresponding arrow adjustments and costs.
- arrow_right_alt
Compute minimum cost if multiple start points are allowed in the top row or left column.