Unique Paths III

Intuition

The grid is tiny (at most 20 squares), so we can afford to explore every possible route exhaustively. The trick is knowing when a route is complete: a valid path must cover the start, the end, and every empty square exactly once. If we count the number of non-obstacle squares before we begin, we can carry a `remaining` counter that decreases by one every time we step onto a fresh square. When we finally arrive at the ending square, the path is valid precisely when `remaining` has reached zero, meaning nothing was skipped. To avoid revisiting squares within a single path, we temporarily mark each visited square as an obstacle and restore it when we backtrack.

Algorithm walkthrough

1. 1Scan the whole grid once to count the empty squares (`0`) and remember the coordinates of the starting square (`1`).
2. 2Set the initial `remaining` count to the number of empty squares plus one, so the start itself is included in the squares that must be covered.
3. 3Run a DFS from the start. If the current cell is out of bounds or an obstacle, return immediately; that branch is dead.
4. 4If the current cell is the ending square, add one to the answer only when `remaining` equals zero, then return without stepping further.
5. 5Otherwise mark the current cell as an obstacle, recurse into all four neighbors with `remaining - 1`, and then restore the cell so sibling branches can reuse it.
6. 6After the DFS finishes, the accumulated count is the number of valid paths.

Implementation

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        empty = 0
        start_r = start_c = 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, start_c = r, c

        self.paths = 0

        def dfs(r: int, c: int, remaining: int) -> None:
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == -1:
                return
            if grid[r][c] == 2:
                if remaining == 0:
                    self.paths += 1
                return
            temp = grid[r][c]
            grid[r][c] = -1
            dfs(r + 1, c, remaining - 1)
            dfs(r - 1, c, remaining - 1)
            dfs(r, c + 1, remaining - 1)
            dfs(r, c - 1, remaining - 1)
            grid[r][c] = temp

        dfs(start_r, start_c, empty + 1)
        return self.paths