LeetCode 题解工作台
不同路径 III
在二维网格 grid 上，有 4 种类型的方格： 1 表示起始方格。且只有一个起始方格。 2 表示结束方格，且只有一个结束方格。 0 表示我们可以走过的空方格。 -1 表示我们无法跨越的障碍。 返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目 。 每一个无障碍方格都要通…
4
题型
6
代码语言
3
相关题
当前训练重点
困难 · 回溯·pruning
答案摘要
我们可以先遍历整个网格，找出起点 $(x, y)$，并且统计空白格的数量 。 接下来，我们可以从起点开始搜索，得到所有的路径数。我们设计一个函数 $dfs(i, j, k)$ 表示从 $(i, j)$ 出发，且当前已经走过的单元格数量为 的路径数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
在二维网格 grid 上，有 4 种类型的方格：
1表示起始方格。且只有一个起始方格。2表示结束方格，且只有一个结束方格。0表示我们可以走过的空方格。-1表示我们无法跨越的障碍。
返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
示例 1：
输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]] 输出：2 解释：我们有以下两条路径： 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2) 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
示例 2：
输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]] 输出：4 解释：我们有以下四条路径： 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3) 2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3) 3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3) 4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
示例 3：
输入：[[0,1],[2,0]] 输出：0 解释： 没有一条路能完全穿过每一个空的方格一次。 请注意，起始和结束方格可以位于网格中的任意位置。
提示：
1 <= grid.length * grid[0].length <= 20
解题思路
方法一：回溯
我们可以先遍历整个网格，找出起点 ，并且统计空白格的数量 。
接下来，我们可以从起点开始搜索，得到所有的路径数。我们设计一个函数 表示从 出发，且当前已经走过的单元格数量为 的路径数。
在函数中，我们首先判断当前单元格是否为终点，如果是，则判断 是否等于 ，如果是，则说明当前路径是一条有效路径，返回 ，否则返回 。
如果当前单元格不是终点，则我们枚举当前单元格的上下左右四个邻接单元格，如果邻接单元格未被访问过，则我们将该邻接单元格标记为已访问，然后继续搜索从该邻接单元格出发的路径数，搜索完成后，我们再将该邻接单元格标记为未访问。在搜索完成后，我们返回所有邻接单元格的路径数之和。
最后，我们返回从起点出发的路径数即可，即 。
时间复杂度 ，空间复杂度 。其中 和 分别为网格的行数和列数。
class Solution:
def uniquePathsIII(self, grid: List[List[int]]) -> int:
def dfs(i: int, j: int, k: int) -> int:
if grid[i][j] == 2:
return int(k == cnt + 1)
ans = 0
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and (x, y) not in vis and grid[x][y] != -1:
vis.add((x, y))
ans += dfs(x, y, k + 1)
vis.remove((x, y))
return ans
m, n = len(grid), len(grid[0])
start = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == 1)
dirs = (-1, 0, 1, 0, -1)
cnt = sum(row.count(0) for row in grid)
vis = {start}
return dfs(*start, 0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Evaluate the candidate's ability to implement a backtracking solution efficiently.
- question_mark
Assess whether the candidate can use bit manipulation to optimize the solution.
- question_mark
Check if the candidate handles base and edge cases effectively in the DFS.
常见陷阱
外企场景- error
Failing to prune invalid paths early, leading to excessive backtracking and inefficient computation.
- error
Not correctly tracking visited squares, either revisiting squares or missing some.
- error
Overcomplicating the solution by not using bit masking for efficient state tracking.
进阶变体
外企场景- arrow_right_alt
Implementing a non-recursive version of the backtracking approach using an explicit stack.
- arrow_right_alt
Extending the problem to grids with multiple starting and ending points.
- arrow_right_alt
Considering non-square grids with arbitrary shapes and obstacles.