深度优先遍历|LeetCode —— 980. 不同路径 III（Python）深度优先遍历|LeetCode算法题

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

1 表示起始方格。且只有一个起始方格。
2 表示结束方格，且只有一个结束方格。
0 表示我们可以走过的空方格。
-1 表示我们无法跨越的障碍。
返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
【深度优先遍历|LeetCode —— 980. 不同路径 III（Python）】来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution: def uniquePathsIII(self, grid): R, C = len(grid), len(grid[0])# 计算行数和列数def neighbors(r, c): for nr, nc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)): if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] % 2 == 0:# 返回可以到达的位置 yield nr, nctodo = 0 for r, row in enumerate(grid): for c, val in enumerate(row): if val != -1: todo += 1# 统计不是障碍的点数 if val == 1:# 起始位置 sr, sc = r, c if val == 2:# 结束位置 tr, tc = r, cself.ans = 0 def dfs(r, c, todo): todo -= 1# 遍历到一个位置，将当前位置变为-1 if todo < 0: return if r == tr and c == tc:# 当到达目标位置同时todo为零 if todo == 0: self.ans += 1 returngrid[r][c] = -1 for nr, nc in neighbors(r, c): dfs(nr, nc, todo) grid[r][c] = 0# 回溯dfs(sr, sc, todo) return self.ans