# LeetCode 980: Unique Paths III

## Problem Restatement

We are given an `m x n` grid.

Each cell has one of four values:

| Value | Meaning |
|---|---|
| `1` | Starting square |
| `2` | Ending square |
| `0` | Empty square we can walk over |
| `-1` | Obstacle we cannot walk over |

There is exactly one starting square and exactly one ending square.

We need to count how many 4-directional walks go from the start to the end while visiting every non-obstacle square exactly once.

A move can go:

```python
up, down, left, right
```

Diagonal moves are not allowed.

The grid has at most `20` cells total, so exhaustive search with backtracking is acceptable. The official statement requires walking over every non-obstacle square exactly once.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A 2D integer grid |
| Output | Number of valid paths |
| Start | Cell with value `1` |
| End | Cell with value `2` |
| Walkable cells | Cells with values `0`, `1`, and `2` |
| Blocked cells | Cells with value `-1` |

Function shape:

```python
def uniquePathsIII(grid: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

```python
grid = [
    [1, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 2, -1],
]
```

There are `4` valid paths.

Answer:

```python
4
```

Example 2:

```python
grid = [
    [1, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 2],
]
```

There are `2` valid paths.

Answer:

```python
2
```

Example 3:

```python
grid = [
    [0, 1],
    [2, 0],
]
```

There is no path that starts at `1`, ends at `2`, and visits every non-obstacle square exactly once.

Answer:

```python
0
```

## First Thought: Try All Paths

This problem asks us to count all valid walks.

The path can move in four directions, and we must avoid revisiting cells.

That means a normal dynamic programming solution for Unique Paths does not fit here. In the earlier Unique Paths problems, movement is restricted to right and down. Here, we can move in all four directions, so the same cell can be reached from many different histories.

The natural method is backtracking:

1. Start from the starting cell.
2. Mark the current cell as visited.
3. Try all four neighboring cells.
4. Continue only if the neighbor is inside the grid and not blocked or visited.
5. When reaching the ending cell, count the path only if every walkable cell has been visited.
6. Undo the visit mark before returning.

## Key Insight

The hard part is knowing whether a path that reaches the ending square is complete.

Reaching the end is not enough.

We must also have visited every non-obstacle square exactly once.

So before DFS starts, count all walkable cells:

```python
walkable = number of cells whose value is not -1
```

Then during DFS, track how many walkable cells remain to be visited.

When we enter a cell, we use one walkable cell:

```python
remaining -= 1
```

When we reach the ending cell, the path is valid only if:

```python
remaining == 0
```

This means the current path has visited all walkable cells exactly once.

## Algorithm

First scan the grid.

During this scan:

1. Find the starting cell.
2. Count all cells that are not obstacles.

Then run DFS from the start.

The DFS state is:

```python
dfs(row, col, remaining)
```

where `remaining` is the number of walkable cells not yet consumed before entering `(row, col)`.

Inside DFS:

1. If the position is outside the grid, return.
2. If the cell is an obstacle or already visited, return.
3. Consume this cell by subtracting `1` from `remaining`.
4. If this cell is the ending cell, return `1` only when `remaining == 0`.
5. Mark the current cell as visited.
6. Search in four directions.
7. Restore the cell before returning.
8. Return the total number of valid paths from this state.

## Correctness

The algorithm starts only from the unique starting cell.

At every DFS call, it rejects positions outside the grid, obstacles, and already visited cells. Therefore, every explored path stays inside the grid, never steps on obstacles, and never visits a cell twice.

Each time DFS enters a valid cell, it decreases `remaining` by `1`. Therefore, `remaining` exactly records how many walkable cells have not yet been included in the current path.

When DFS reaches the ending cell, it counts the path only if `remaining == 0`. This condition means every walkable cell has been visited. Since the algorithm also prevents revisiting cells, the path has visited every non-obstacle square exactly once.

Conversely, consider any valid path from the start to the end that visits every non-obstacle square exactly once. At each step, the next cell is inside the grid, not an obstacle, and not yet visited, so DFS will include that move among its four-direction choices. Thus every valid path is explored and counted.

Since the algorithm counts exactly the valid paths and rejects all invalid paths, it returns the correct answer.

## Complexity

Let `k` be the number of walkable cells.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(4^k)` | In the worst case, each step can branch in up to four directions |
| Space | `O(k)` | Recursion depth is at most the number of walkable cells |

Because the total number of grid cells is at most `20`, this exponential backtracking is acceptable.

## Implementation

```python
class Solution:
    def uniquePathsIII(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        start_row = 0
        start_col = 0
        walkable = 0

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != -1:
                    walkable += 1

                if grid[r][c] == 1:
                    start_row = r
                    start_col = c

        def dfs(r: int, c: int, remaining: int) -> int:
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return 0

            if grid[r][c] == -1:
                return 0

            remaining -= 1

            if grid[r][c] == 2:
                if remaining == 0:
                    return 1
                return 0

            original = grid[r][c]
            grid[r][c] = -1

            total = 0
            total += dfs(r + 1, c, remaining)
            total += dfs(r - 1, c, remaining)
            total += dfs(r, c + 1, remaining)
            total += dfs(r, c - 1, remaining)

            grid[r][c] = original

            return total

        return dfs(start_row, start_col, walkable)
```

## Code Explanation

We first get the grid dimensions:

```python
rows = len(grid)
cols = len(grid[0])
```

Then we scan the grid:

```python
for r in range(rows):
    for c in range(cols):
```

Every cell that is not an obstacle must be visited exactly once:

```python
if grid[r][c] != -1:
    walkable += 1
```

We also record the starting position:

```python
if grid[r][c] == 1:
    start_row = r
    start_col = c
```

The DFS rejects invalid positions:

```python
if r < 0 or r >= rows or c < 0 or c >= cols:
    return 0

if grid[r][c] == -1:
    return 0
```

We use the current cell:

```python
remaining -= 1
```

If we reached the ending cell, the path is valid only if all walkable cells have been used:

```python
if grid[r][c] == 2:
    if remaining == 0:
        return 1
    return 0
```

We mark the current cell as visited by temporarily setting it to `-1`:

```python
original = grid[r][c]
grid[r][c] = -1
```

Then we try all four directions:

```python
total = 0
total += dfs(r + 1, c, remaining)
total += dfs(r - 1, c, remaining)
total += dfs(r, c + 1, remaining)
total += dfs(r, c - 1, remaining)
```

After exploring, we restore the cell:

```python
grid[r][c] = original
```

This restoration is the backtracking step. It lets other paths use this cell later.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.uniquePathsIII([
        [1, 0, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 2, -1],
    ]) == 4

    assert s.uniquePathsIII([
        [1, 0, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 2],
    ]) == 2

    assert s.uniquePathsIII([
        [0, 1],
        [2, 0],
    ]) == 0

    assert s.uniquePathsIII([
        [1, 2],
    ]) == 1

    assert s.uniquePathsIII([
        [1, -1],
        [0, 2],
    ]) == 1

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]` | `4` | Standard case with one obstacle |
| `[[1,0,0,0],[0,0,0,0],[0,0,0,2]]` | `2` | Standard case without obstacle |
| `[[0,1],[2,0]]` | `0` | Cannot visit every square exactly once |
| `[[1,2]]` | `1` | Direct start-to-end path |
| `[[1,-1],[0,2]]` | `1` | Must go around the obstacle |