1
class Solution:
2
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
3
        ans, empty = 0, 1
4

5
        def dfs(grid: List[List[int]], row: int, col: int, count: int, visited) -> None:
6
            if (
7
                row >= len(grid)
8
                or col >= len(grid[0])
9
                or row < 0
10
                or col < 0
11
                or grid[row][col] == -1
12
            ):
13
                return
14
            nonlocal ans
15
            if grid[row][col] == 2:
16
                if empty == count:
17
                    ans += 1
18
                return
19
            if (row, col) not in visited:
20
                visited.add((row, col))
21
                dfs(grid, row + 1, col, count + 1, visited)
22
                dfs(grid, row - 1, col, count + 1, visited)
23
                dfs(grid, row, col + 1, count + 1, visited)
24
                dfs(grid, row, col - 1, count + 1, visited)
25
                visited.remove((row, col))
26

27
        row, col = 0, 0
28
        for i in range(len(grid)):
29
            for j in range(len(grid[0])):
30
                if grid[i][j] == 1:
31
                    row, col = i, j
32
                elif grid[i][j] == 0:
33
                    empty += 1
34
        dfs(grid, row, col, 0, set())
35
        return ans