不同路径 III

标签: 位运算 数组 回溯 矩阵

难度: Hard

在二维网格 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

Submission

运行时间: 28 ms

内存: 16.1 MB

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        def dfs(x, y, left):
            if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] < 0:
                return 0
            if grid[x][y] == 2:
                return left == 0
            grid[x][y] = -1
            ans = dfs(x-1,y,left-1) + dfs(x+1, y, left-1) + dfs(x, y-1, left-1) + dfs(x, y+1, left-1)
            grid[x][y] = 0
            return ans
        ab = sum(row.count(0) for row in grid)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    return dfs(i, j, ab+1)

Explain

题解采用深度优先搜索（DFS）策略，通过递归来探索所有可能的路径。首先，算法寻找起始点（值为1的格子），并计算网格中空白格子（值为0）的数量。之后，从起始点出发，向四个方向探索，每走过一个空白格子，就将其标记为不可再走（设为-1）。如果到达终点（值为2的格子），检查是否所有空白格子都已经走过，即剩余格子数left是否为0。如果是，说明找到了一条有效路径。每次探索完成后，将当前格子重置回可走状态，以便其他路径探索时使用。最终，返回从起始点到终点的所有有效路径的数量。

时间复杂度: O(4^k)

空间复杂度: O(k)

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        def dfs(x, y, left):
            if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] < 0:
                return 0
            if grid[x][y] == 2:
                return left == 0
            grid[x][y] = -1
            ans = dfs(x-1,y,left-1) + dfs(x+1, y, left-1) + dfs(x, y-1, left-1) + dfs(x, y+1, left-1)
            grid[x][y] = 0
            return ans
        ab = sum(row.count(0) for row in grid)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    return dfs(i, j, ab+1)

Explore

在这个问题中，我们的目标是找到一条从起点到终点的路径，该路径必须经过所有的空白格子（值为0的格子）。因此，当我们到达终点（值为2的格子）时，我们需要检查是否所有的空白格子都已经被走过。剩余格子数left是在递归过程中跟踪未被访问的空白格子的数量。如果left为0，这意味着所有空白格子都已经被访问过，因此这条路径是有效的。如果left不为0，说明还有空白格子未被访问，因此这条路径是无效的。

在深度优先搜索（DFS）中，为了确保不越界并且不走进障碍格子，我们在递归函数的开始部分进行检查：如果坐标(x, y)超出网格的边界，或者grid[x][y]的值小于0（意味着该格子是障碍或已经被访问过），则递归函数立即返回0，表示从这个格子出发无法形成有效的路径。这种检查确保了DFS只在合法和可行的路径上进行。

在DFS过程中，我们暂时将走过的格子标记为-1，以避免在当前路径搜索中重复走过相同的格子。一旦完成从某个格子出发的所有可能的路径探索，我们需要将这个格子重置为0（可走状态），以便在探索其他可能的路径时该格子可以再次被使用。这种做法是回溯算法的一部分，它允许我们探索所有可能的路径组合，确保每种可能都被考虑到。

是的，题解中的方法确实通过确保每个格子在每条路径中最多被访问一次来避免不必要的重复计算。通过将走过的格子标记为-1，我们阻止了在同一路径搜索中对同一个格子的重复访问，这提高了效率。此外，这种策略也意味着每条可能的路径都是独立考虑的，没有重复计算同一路径。这种方法有效地降低了计算复杂度，尤其是在大规模网格中。