0980. 不同路径 III

ITCharge大约 3 分钟

---

0980. 不同路径 III

标签：位运算、数组、回溯、矩阵
难度：困难

题目链接

0980. 不同路径 III - 力扣

题目大意

描述：

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

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

要求：

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

说明：

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
$1 \le grid.length \times grid[0].length \le 20$ 。

示例：

示例 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)

解题思路

思路 1：回溯

使用回溯法遍历所有可能的路径，统计从起点到终点且经过所有空方格的路径数量。

首先遍历网格，找到起点位置，统计空方格的数量（包括起点和终点）。
从起点开始进行深度优先搜索（DFS）：
- 标记当前方格为已访问。
- 如果到达终点，检查是否经过了所有空方格。
- 否则，向四个方向继续搜索。
- 回溯时，恢复当前方格的状态。
返回满足条件的路径数量。

思路 1：代码

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        start_x = start_y = 0
        empty_count = 0
        
        # 找到起点，统计空方格数量
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    start_x, start_y = i, j
                if grid[i][j] != -1:
                    empty_count += 1
        
        self.result = 0
        
        def dfs(x, y, count):
            # 到达终点
            if grid[x][y] == 2:
                # 检查是否经过了所有空方格
                if count == empty_count:
                    self.result += 1
                return
            
            # 标记为已访问
            temp = grid[x][y]
            grid[x][y] = -1
            
            # 向四个方向搜索
            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != -1:
                    dfs(nx, ny, count + 1)
            
            # 回溯
            grid[x][y] = temp
        
        dfs(start_x, start_y, 1)
        return self.result

思路 1：复杂度分析

时间复杂度： $O(4^{m \times n})$ ，其中 $m$ 和 $n$ 是网格的行数和列数。最坏情况下需要遍历所有可能的路径。
空间复杂度： $O(m \times n)$ ，递归调用栈的深度最多为网格中方格的数量。