980. Unique Paths III (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        self.result = 0
        m, n = len(grid), len(grid[0])
        count = 0
        start = None
        for i in range(m):
            for j in range(n):
                if grid[i][j] == -1:
                    count += 1
                elif grid[i][j] == 1:
                    start = (i, j)
        valid = m * n - count
        def dfs(i, j, seen):
            if grid[i][j] == 2:
                if len(seen) == valid:
                    self.result += 1
            else:
                for dx, dy in (0, 1), (1, 0), (0, -1), (-1, 0):
                    x, y = i + dx, j + dy
                    if 0 <= x < m and 0 <= y < n:
                        if grid[x][y] != -1 and (x, y) not in seen:
                            dfs(x, y, seen | {(x, y)})
        dfs(start[0], start[1], {start})
        return self.result