LeetCode 题解工作台
网格图中最少访问的格子数
给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。 当你在格子 (i, j) 的时候，你可以移动到以下格子之一： 满足 j 的格子 (i, k) （向右移动），或者 满足 i 的格子 (k, j) （向下移动）。 请你返回到达 右下角 格子…
8
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们记网格的行数为 ，列数为 ，定义 表示从坐标 $(0, 0)$ 移动到坐标 $(i, j)$ 的最短距离，初始时 $dist[0][0] = 1$，其它 。 对于每个格子 $(i, j)$，它可以从上边或者左边的格子移动过来。如果是从上边的格子 $(i', j)$ 移动过来，其中 $0 \leq i' \lt i$，那么 $(i', j)$ 需要满足 $grid[i'][j] + i' \g…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。
当你在格子 (i, j) 的时候，你可以移动到以下格子之一：
- 满足
j < k <= grid[i][j] + j的格子(i, k)（向右移动），或者 - 满足
i < k <= grid[i][j] + i的格子(k, j)（向下移动）。
请你返回到达 右下角 格子 (m - 1, n - 1) 需要经过的最少移动格子数，如果无法到达右下角格子，请你返回 -1 。
示例 1：
输入：grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]] 输出：4 解释：上图展示了到达右下角格子经过的 4 个格子。
示例 2：
输入：grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]] 输出：3 解释：上图展示了到达右下角格子经过的 3 个格子。
示例 3：
输入：grid = [[2,1,0],[1,0,0]] 输出：-1 解释：无法到达右下角格子。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 1050 <= grid[i][j] < m * ngrid[m - 1][n - 1] == 0
解题思路
方法一：优先队列
我们记网格的行数为 ，列数为 ，定义 表示从坐标 移动到坐标 的最短距离，初始时 ，其它 。
对于每个格子 ，它可以从上边或者左边的格子移动过来。如果是从上边的格子 移动过来，其中 ，那么 需要满足 ，我们要从这些格子中选择一个距离最近的格子。
因此，我们可以对每一列 维护一个优先队列（小根堆），优先队列中每个元素是一个二元组 ，表示从坐标 移动到坐标 的最短距离为 。当我们考虑坐标 时，我们只需要从优先队列中取出队头元素 ，如果 ，那么就可以从坐标 移动到坐标 ，此时我们就可以更新 的值，即 ，并将 加入到优先队列中。
同理，我们可以对每一行 维护一个优先队列，然后进行与上述类似的操作。
最终，我们可以得到从坐标 移动到坐标 的最短距离 ，即为答案。
时间复杂度 ，空间复杂度 。其中 和 分别为网格的行数和列数。
class Solution:
def minimumVisitedCells(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dist = [[-1] * n for _ in range(m)]
dist[0][0] = 1
row = [[] for _ in range(m)]
col = [[] for _ in range(n)]
for i in range(m):
for j in range(n):
while row[i] and grid[i][row[i][0][1]] + row[i][0][1] < j:
heappop(row[i])
if row[i] and (dist[i][j] == -1 or dist[i][j] > row[i][0][0] + 1):
dist[i][j] = row[i][0][0] + 1
while col[j] and grid[col[j][0][1]][j] + col[j][0][1] < i:
heappop(col[j])
if col[j] and (dist[i][j] == -1 or dist[i][j] > col[j][0][0] + 1):
dist[i][j] = col[j][0][0] + 1
if dist[i][j] != -1:
heappush(row[i], (dist[i][j], j))
heappush(col[j], (dist[i][j], i))
return dist[-1][-1]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity ranges from O(m _n) in the optimized BFS and monotonic stack solution to higher if naive scanning is used. Space complexity is O(m_ n) for storing the distance matrix, plus additional memory for BFS queues or stacks. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask how to efficiently compute dis[i][j] for large grids without exceeding memory limits.
- question_mark
Probe understanding of BFS versus DP trade-offs in a matrix with jump constraints.
- question_mark
Check if candidates notice the importance of monotonic structures to skip redundant updates.
常见陷阱
外企场景- error
Trying to scan every possible cell naively, leading to TLE in large grids.
- error
Failing to correctly update dis[i][j] when multiple paths reach the same cell.
- error
Ignoring the jump constraints of grid[i][j] and assuming simple adjacency moves.
进阶变体
外企场景- arrow_right_alt
Grid with weighted cells where cost is added instead of counting steps, requiring modified DP.
- arrow_right_alt
Allowing diagonal jumps in addition to row and column moves, increasing state space.
- arrow_right_alt
Dynamic grid values where jumps change after each move, necessitating adaptive DP or BFS.