LeetCode 1293. 网格中的最短路径 题目描述 在一个 m x n 的网格中，每个单元格要么是空地（用 0 表示），要么是障碍物（用 1 表示）。你从左上角 (0, 0) 出发，希望到达右下角 (m-1, n-1) 。你可以向上、下、左、右四个方向移动。在穿越网格时，你最多可以消除 k 个障碍物（即从 1 变成 0 的格子）。请你找出从起点到终点的最短路径长度（即移动的步数）。如果无法到达，则返回 -1 。 例子 输入： grid = [ [ 0,0,0 ], [ 1,1,0 ], [ 0,0,0 ], [ 0,1,1 ], [ 0,0,0 ] ], k = 1 输出：6 解释：最短路径是向右 -> 向右 -> 向下 -> 向下 -> 向左 -> 向下，总步数为6，其中在第三行第二列（从0开始计数，坐标(2,1)）的障碍物被消除一次。 解题过程 这个题目的核心是在网格中寻找最短路径，但引入了“最多可消除k个障碍物”的条件，这增加了状态维度。我们可以将其转化为一个带状态的最短路径搜索问题。 步骤1：问题分析 如果没有障碍物消除限制，这是一个标准的BFS（广度优先搜索）求最短路径问题。 加入消除障碍物的限制后，到达同一个格子时，如果已消除的障碍物数量不同，那么后续的移动能力也不同。因此，我们不能仅仅用 (x, y) 来表示状态，还需要加上“当前已消除的障碍物数量”这个维度，即状态为 (x, y, eliminated) ，其中 eliminated 表示从起点到当前格子已经消除了多少个障碍物。 由于消除障碍物数量有限制， eliminated 的范围是 0 到 k 。当遇到障碍物时，只有 eliminated < k 才能尝试消除并继续移动。 步骤2：状态定义与BFS队列 定义状态： (x, y, eliminated) ，表示当前位于 (x, y) ，并且已经消除了 eliminated 个障碍物。 使用BFS队列，每个元素是一个状态加上步数： (x, y, eliminated, steps) 。初始状态为 (0, 0, 0, 0) ，表示在起点，尚未消除障碍物，步数为0。 需要记录访问过的状态，避免重复访问。用一个三维数组 visited[x][y][eliminated] 来记录状态 (x, y, eliminated) 是否已访问。 步骤3：BFS搜索过程 从队列中取出当前状态 (x, y, eliminated, steps) 。 如果 (x, y) 是终点 (m-1, n-1) ，则立即返回 steps ，因为BFS保证第一次到达终点的路径最短。 遍历四个方向（上、下、左、右），计算下一个位置 (nx, ny) 。 检查新位置是否在网格内： 如果 grid[nx][ny] == 0 （空地）： 新状态为 (nx, ny, eliminated) 。如果这个状态未访问过，则标记为已访问，并加入队列： (nx, ny, eliminated, steps+1) 。 如果 grid[nx][ny] == 1 （障碍物）： 检查是否还能消除障碍物：即 eliminated < k 。 如果能消除，则新状态为 (nx, ny, eliminated+1) 。如果未访问过，则标记为已访问，并加入队列： (nx, ny, eliminated+1, steps+1) 。 步骤4：边界与细节处理 注意起始点可能是障碍物吗？根据题目描述，起点和终点一般是空地（0），但即使起点是障碍物，我们也可以立即消除（如果k>=1），但题目通常保证起点和终点是空地。 如果BFS队列被清空仍未到达终点，说明无法在消除最多k个障碍物的条件下到达终点，返回-1。 优化：当 eliminated 已经达到k时，后续只能走空地，不能走障碍物了。 步骤5：复杂度分析 状态总数： m * n * (k+1) ，因为每个格子可能有不同的已消除数量状态。 每个状态最多扩展4个方向，因此时间复杂度为 O(m * n * k)，空间复杂度也为 O(m * n * k)。 举例说明 以题目例子为例，网格为5x3，k=1。 初始状态 (0,0,0) 入队。 第一步从(0,0)可以走到(0,1)和(1,0)：(0,1)是空地，状态(0,1,0)入队；(1,0)是障碍物，但k=1，可以消除，状态(1,0,1)入队。 继续BFS，注意当状态中的eliminated=1时，后续不能再消除障碍物了。 最终，在步数6时，以状态(4,2,1)到达终点（途中在(2,1)处消除了一个障碍物），返回6。 总结 这道题是BFS的变种，关键是将“已消除障碍物数量”作为状态的一部分，从而在搜索时能够根据当前剩余消除能力做出不同的移动决策。通过三维的visited数组避免重复状态，确保BFS能找到最短路径。