LeetCode 980: Unique Paths III

Problem Restatement

We are given an m x n grid.

Each cell has one of four values:

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:

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

Function shape:

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

Examples

Example 1:

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

There are 4 valid paths.

Answer:

4

Example 2:

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

There are 2 valid paths.

Answer:

2

Example 3:

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:

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:

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:

remaining -= 1

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

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:

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.

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

Implementation

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:

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

Then we scan the grid:

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

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

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

We also record the starting position:

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

The DFS rejects invalid positions:

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:

remaining -= 1

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

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:

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

Then we try all four directions:

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:

grid[r][c] = original

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

Testing

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