Unique Paths III Python Solution with Tests

lcpy gen -n 980   # by problem number
lcpy gen -s unique_paths_iii   # by problem name

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:
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)

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

Input: grid = [[0,1],[2,0]]
Output: 0
Explanation: There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.

class Solution:
    # Time: O(3^(m*n)) backtracking over non-obstacle cells
    # Space: O(m*n) for the visited set and recursion stack
    def unique_paths_iii(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        empty = 0
        start = (0, 0)
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 0:
                    empty += 1
                elif grid[r][c] == 1:
                    start = (r, c)

        seen = {start}
        count = 0

        def dfs(r: int, c: int) -> None:
            nonlocal count
            if grid[r][c] == 2:
                if len(seen) == empty + 2:
                    count += 1
                return
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                in_bounds = 0 <= nr < rows and 0 <= nc < cols
                if in_bounds and grid[nr][nc] != -1 and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    dfs(nr, nc)
                    seen.discard((nr, nc))

        dfs(*start)
        return count