980. 不同路径 III（Rating 1830）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

980. 不同路径 III

Rating 1830

思路

dfs回溯即可。

代码

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        x, y = -1, -1
        cnt0 = 1 # 统计0的个数，将终点“2”也算做一个0，因此从1开始
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0: # 统计0的个数
                    cnt0 += 1
                elif grid[i][j] == 1: # 找到起点
                    x, y = i, j
        vis = {(x, y)} # 记录访问过的位置
        dir = [-1, 0, 1, 0, -1]
        def dfs(x : int, y : int, cnt : int, vis : set) -> int:
            if grid[x][y] == 2:
                return cnt == 0
            ret = 0
            for d in range(4):
                nx = x + dir[d]
                ny = y + dir[d + 1]
                if nx < 0 or nx >= m or ny < 0 or ny >= n:
                    continue
                if grid[nx][ny] == -1:
                    continue
                if (nx, ny) in vis:
                    continue
                vis.add((nx, ny))
                ret += dfs(nx, ny, cnt - 1, vis)
                vis.remove((nx, ny))
            return ret
        return dfs(x, y, cnt0, vis)