在二维网格 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)
class Solution: def uniquePathsIII(self, grid: List[List[int]]) -> int: def backtrack(i, j, leave): if grid[i][j] == 2 and leave == 0: # 找到符合条件的路径 self.res += 1 return visited[i][j] = True leave -= 1 for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]: if 0 <= x < row and 0 <= y < col and not visited[x][y] and grid[x][y] >= 0: backtrack(x, y, leave) # drill down到下一层 visited[i][j] = False self.res = 0 # 统计路径的数目 row = len(grid) col = len(grid[0]) leave = row * col # 还剩下的点 visited = [[False] * col for _ in range(row)] # 标记某个点是否被访问过 for i in range(row): for j in range(col): if grid[i][j] == 1: # 保存起始点 start = [i, j] elif grid[i][j] == -1 or grid[i][j] == 2: # 此时,只留下值是0和1的点的个数 leave -= 1 backtrack(start[0], start[1], leave) return self.res