> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Unique Paths III Python Solution with Tests

> Tested Python solution for LeetCode 980 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 980, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Backtracking](/catalog/topics/backtracking), [Bit Manipulation](/catalog/topics/bit-manipulation), [Matrix](/catalog/topics/matrix). [View on LeetCode](https://leetcode.com/problems/unique-paths-iii/description/).

Generate this problem as a practice environment: tested reference solution, 22 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 980   # by problem number
lcpy gen -s unique_paths_iii   # by problem name
```

## Problem

You are given an `m x n` integer array `grid` where `grid[i][j]` could be:

* `1` representing the starting square. There is exactly one starting square.
* `2` representing the ending square. There is exactly one ending square.
* `0` representing empty squares we can walk over.
* `-1` representing obstacles that we cannot walk over.

Return *the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once*.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/08/02/lc-unique1.jpg)

```
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)
```

![Example 2](https://assets.leetcode.com/uploads/2021/08/02/lc-unique2.jpg)

```
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)
```

![Example 3](https://assets.leetcode.com/uploads/2021/08/02/lc-unique3-.jpg)

```
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.
```

### Constraints

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 20`
* `1 <= m * n <= 20`
* `-1 <= grid[i][j] <= 2`
* There is exactly one starting cell and one ending cell.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/unique_paths_iii/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/unique_paths_iii/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
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
```

## Complexity

| Time | Space |
| - | - |
| O(3^(m\*n)) backtracking over non-obstacle cells | O(m\*n) for the visited set and recursion stack |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.