LeetCode 980. 不同路径 III

字数 2591 2025-10-26 21:06:54

LeetCode 980. 不同路径 III

题目描述

在二维网格 grid 上，有 4 种类型的方格：

1 表示起点方格。且只有一个起点方格。
2 表示终点方格。且只有一个终点方格。
0 表示我们可以走过的空方格。
-1 表示我们无法跨越的障碍方格。

要求：返回在网格中从起点到终点的不同路径的数目，其中每一条路径应该走过每一个空方格恰好一次。

示例 1：
输入：grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出：2
解释：我们有以下两条路径：

(0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(1,2)->(1,1)->(1,0)->(2,0)->(2,1)->(2,2)
(0,0)->(1,0)->(2,0)->(2,1)->(1,1)->(0,1)->(0,2)->(0,3)->(1,3)->(1,2)->(2,2)

解题过程

这个问题的核心约束是“走过每一个空方格恰好一次”，这意味着路径必须覆盖所有非障碍、非终点的格子。这提示我们需要使用回溯算法（一种深度优先搜索）来探索所有可能的路径。

第一步：问题分析与状态定义

目标：从起点出发，走到终点，并且路径必须经过所有标记为 0 的格子（以及终点 2）一次且仅一次。
关键变量：
- 总步数：我们需要走过的格子总数。这等于网格中 0 的个数（所有空方格） + 1（终点方格）。知道了总步数，当我们走到终点时，可以通过判断已走步数是否等于总步数，来确认是否走完了所有空方格。
- 起点坐标：我们需要记录起点 (start_row, start_col) 的位置，作为搜索的起点。
- 已访问状态：在探索路径时，我们需要标记哪些格子已经走过了，避免重复访问。通常用一个与网格同尺寸的二维布尔数组 visited 来实现。
算法选择：由于需要找出所有满足条件的路径（而不是最短路径），深度优先搜索（DFS）结合回溯是自然的选择。我们会从起点开始，尝试朝四个方向（上、下、左、右）移动，如果新位置是合法的（在网格内、不是障碍、未被访问），就继续递归搜索。当到达终点时，检查是否已走过所有必需格子。搜索完一个分支后，需要回溯（撤销当前选择），以尝试其他可能性。

第二步：详细解题步骤

初始化：
- 遍历整个网格 grid。
- 记录起点 (sr, sc) 的坐标。
- 计算总步数 steps，初始值为 1（因为终点 2 也必须被走过）。在遍历过程中，每当遇到一个 0，就将 steps 加 1。
- 初始化一个与 grid 大小相同的 visited 数组，所有值设为 false。
深度优先搜索（DFS）函数设计：
- 函数签名：dfs(row, col, steps_remaining, visited, grid)
  - (row, col)：当前所在的格子坐标。
  - steps_remaining：剩余需要走的步数（即还未访问的 0 和终点 2 的数量）。
  - visited：记录访问状态的数组。
  - grid：输入的网格。
- 基准情况（递归终止条件）：
  - 如果当前格子是终点（grid[row][col] == 2）：
    - 如果 steps_remaining == 1（因为走到终点这一步本身消耗了最后一步），说明我们恰好走完了所有必需格子，找到一条有效路径，返回 1。
    - 否则，这条路径虽然到了终点，但没有走完所有格子，是无效路径，返回 0。
  - 如果当前格子不是终点，但已经被访问过，或者是障碍物（-1），返回 0（无效路径）。
- 递归过程：
  - 标记当前格子 (row, col) 为已访问。
  - 初始化一个计数器 count = 0，用于累计从当前格子出发能找到的有效路径数。
  - 遍历当前格子的四个邻居方向（例如：[(0,1), (1,0), (0,-1), (-1,0)]）。
    - 计算新坐标 (newRow, newCol)。
    - 如果新坐标在网格范围内，则递归调用 DFS 函数：count += dfs(newRow, newCol, steps_remaining - 1, visited, grid)。
  - 回溯：在尝试完当前格子的所有可能方向后，撤销对当前格子的访问标记（visited[row][col] = false）。这一步至关重要，它确保了在返回上一层递归后，其他路径仍然可以访问这个格子。
  - 返回计数器 count，即从当前状态出发能找到的所有有效路径数。
启动搜索：从起点 (sr, sc) 调用 DFS 函数，初始的 steps_remaining 就是之前计算的总步数 steps。

第三步：举例说明（以示例1为例）

网格：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]

起点 1 在 (0,0)。
终点 2 在 (2,2)。
障碍 -1 在 (2,3)。
空方格 0 有 7 个。
总步数 steps = 7(空方格) + 1(终点) = 8。

搜索过程简述（简化版）：

从 (0,0) 开始，标记为已访问。剩余步数=7。
尝试四个方向。比如先向右到 (0,1)，标记，剩余步数=6。
继续递归深入。如果某条路径最终到达了 (2,2) 且此时剩余步数恰好为1（即已走步数=8），则计数+1。
如果某条路径提前到达终点但剩余步数不为1，或者走入死胡同，则回溯。例如，从 (0,0) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (1,2) -> (1,1) -> (1,0) -> (2,0) -> (2,1)，此时发现无法到达终点（因为 (2,2) 被 (2,1) 和 (1,1) 包围，但 (1,1) 已访问过），则开始回溯，撤销这些点的访问标记，尝试其他方向。
算法会系统地探索所有可能路径，最终找到两条满足条件的路径，返回结果 2。

总结
这道题是回溯/DFS 的一个经典应用，其难点在于理解“必须走完所有空方格”这一约束条件，并通过“剩余步数”来巧妙地进行判断。回溯步骤（撤销访问标记）是保证能探索所有可能性的关键。

LeetCode 980. 不同路径 III 题目描述在二维网格 grid 上，有 4 种类型的方格： 1 表示起点方格。且只有一个起点方格。 2 表示终点方格。且只有一个终点方格。 0 表示我们可以走过的空方格。 -1 表示我们无法跨越的障碍方格。要求：返回在网格中从起点到终点的不同路径的数目，其中每一条路径应该走过每一个空方格恰好一次。示例 1：输入：grid = [ [ 1,0,0,0],[ 0,0,0,0],[ 0,0,2,-1] ] 输出：2 解释：我们有以下两条路径： (0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(1,2)->(1,1)->(1,0)->(2,0)->(2,1)->(2,2) (0,0)->(1,0)->(2,0)->(2,1)->(1,1)->(0,1)->(0,2)->(0,3)->(1,3)->(1,2)->(2,2) 解题过程这个问题的核心约束是“走过每一个空方格恰好一次”，这意味着路径必须覆盖所有非障碍、非终点的格子。这提示我们需要使用回溯算法（一种深度优先搜索）来探索所有可能的路径。第一步：问题分析与状态定义目标：从起点出发，走到终点，并且路径必须经过所有标记为 0 的格子（以及终点 2 ）一次且仅一次。关键变量：总步数：我们需要走过的格子总数。这等于网格中 0 的个数（所有空方格） + 1 （终点方格）。知道了总步数，当我们走到终点时，可以通过判断已走步数是否等于总步数，来确认是否走完了所有空方格。起点坐标：我们需要记录起点 (start_row, start_col) 的位置，作为搜索的起点。已访问状态：在探索路径时，我们需要标记哪些格子已经走过了，避免重复访问。通常用一个与网格同尺寸的二维布尔数组 visited 来实现。算法选择：由于需要找出所有满足条件的路径（而不是最短路径），深度优先搜索（DFS）结合回溯是自然的选择。我们会从起点开始，尝试朝四个方向（上、下、左、右）移动，如果新位置是合法的（在网格内、不是障碍、未被访问），就继续递归搜索。当到达终点时，检查是否已走过所有必需格子。搜索完一个分支后，需要回溯（撤销当前选择），以尝试其他可能性。第二步：详细解题步骤初始化：遍历整个网格 grid 。记录起点 (sr, sc) 的坐标。计算总步数 steps ，初始值为 1（因为终点 2 也必须被走过）。在遍历过程中，每当遇到一个 0 ，就将 steps 加 1。初始化一个与 grid 大小相同的 visited 数组，所有值设为 false 。深度优先搜索（DFS）函数设计：函数签名： dfs(row, col, steps_remaining, visited, grid) (row, col) ：当前所在的格子坐标。 steps_remaining ：剩余需要走的步数（即还未访问的 0 和终点 2 的数量）。 visited ：记录访问状态的数组。 grid ：输入的网格。基准情况（递归终止条件）：如果当前格子是终点（ grid[row][col] == 2 ）：如果 steps_remaining == 1 （因为走到终点这一步本身消耗了最后一步），说明我们恰好走完了所有必需格子，找到一条有效路径，返回 1。否则，这条路径虽然到了终点，但没有走完所有格子，是无效路径，返回 0。如果当前格子不是终点，但已经被访问过，或者是障碍物（ -1 ），返回 0（无效路径）。递归过程：标记当前格子 (row, col) 为已访问。初始化一个计数器 count = 0 ，用于累计从当前格子出发能找到的有效路径数。遍历当前格子的四个邻居方向（例如： [(0,1), (1,0), (0,-1), (-1,0)] ）。计算新坐标 (newRow, newCol) 。如果新坐标在网格范围内，则递归调用 DFS 函数： count += dfs(newRow, newCol, steps_remaining - 1, visited, grid) 。回溯：在尝试完当前格子的所有可能方向后，撤销对当前格子的访问标记（ visited[row][col] = false ）。这一步至关重要，它确保了在返回上一层递归后，其他路径仍然可以访问这个格子。返回计数器 count ，即从当前状态出发能找到的所有有效路径数。启动搜索：从起点 (sr, sc) 调用 DFS 函数，初始的 steps_remaining 就是之前计算的总步数 steps 。第三步：举例说明（以示例1为例）网格： [[1,0,0,0],[0,0,0,0],[0,0,2,-1]] 起点 1 在 (0,0)。终点 2 在 (2,2)。障碍 -1 在 (2,3)。空方格 0 有 7 个。总步数 steps = 7(空方格) + 1(终点) = 8 。搜索过程简述（简化版）：从 (0,0) 开始，标记为已访问。剩余步数=7。尝试四个方向。比如先向右到 (0,1)，标记，剩余步数=6。继续递归深入。如果某条路径最终到达了 (2,2) 且此时剩余步数恰好为1（即已走步数=8），则计数+1。如果某条路径提前到达终点但剩余步数不为1，或者走入死胡同，则回溯。例如，从 (0,0) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (1,2) -> (1,1) -> (1,0) -> (2,0) -> (2,1)，此时发现无法到达终点（因为 (2,2) 被 (2,1) 和 (1,1) 包围，但 (1,1) 已访问过），则开始回溯，撤销这些点的访问标记，尝试其他方向。算法会系统地探索所有可能路径，最终找到两条满足条件的路径，返回结果 2。总结这道题是回溯/DFS 的一个经典应用，其难点在于理解“必须走完所有空方格”这一约束条件，并通过“剩余步数”来巧妙地进行判断。回溯步骤（撤销访问标记）是保证能探索所有可能性的关键。