Unique Paths III

Problem#

Grid with 1 = start, 2 = end, 0 = walkable, -1 = obstacle. Return the number of distinct paths from start to end that visit every 0 exactly once.

Examples#

[[1,0,0,0],[0,0,0,0],[0,0,2,-1]] → 2

Constraints#

1 <= m, n <= 20, total walkable ≤ 20.

Approach#

DFS from start. Count walkable cells (0s + start). Each step: mark current as visited (-1), recurse to 4 neighbors, restore. Count paths reaching end with all walkables visited.

Solution#

class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int sr = 0, sc = 0, walk = 1; // include start
        for (int r = 0; r < m; ++r) for (int c = 0; c < n; ++c) {
            if (grid[r][c] == 1) { sr = r; sc = c; }
            else if (grid[r][c] == 0) ++walk;
        }
        int ans = 0;
        function<void(int,int,int)> dfs = [&](int r, int c, int remaining) {
            if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == -1) return;
            if (grid[r][c] == 2) { if (remaining == 0) ++ans; return; }
            int saved = 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] = saved;
        };
        dfs(sr, sc, walk - 1);
        return ans;
    }
};

func uniquePathsIII(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    sr, sc, walk := 0, 0, 1 // include start
    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if grid[r][c] == 1 {
                sr, sc = r, c
            } else if grid[r][c] == 0 {
                walk++
            }
        }
    }
    ans := 0
    var dfs func(r, c, remaining int)
    dfs = func(r, c, remaining int) {
        if r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == -1 {
            return
        }
        if grid[r][c] == 2 {
            if remaining == 0 {
                ans++
            }
            return
        }
        saved := 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] = saved
    }
    dfs(sr, sc, walk-1)
    return ans
}

from typing import List

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        sr = sc = 0
        walk = 1  # include start
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    sr, sc = r, c
                elif grid[r][c] == 0:
                    walk += 1
        self.ans = 0

        def dfs(r: int, c: int, remaining: int) -> None:
            if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == -1:
                return
            if grid[r][c] == 2:
                if remaining == 0:
                    self.ans += 1
                return
            saved = 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] = saved

        dfs(sr, sc, walk - 1)
        return self.ans

function uniquePathsIII(grid) {
    const m = grid.length, n = grid[0].length;
    let sr = 0, sc = 0, walk = 1; // include start
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 1) { sr = r; sc = c; }
            else if (grid[r][c] === 0) walk++;
        }
    }
    let ans = 0;
    const dfs = (r, c, remaining) => {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] === -1) return;
        if (grid[r][c] === 2) { if (remaining === 0) ans++; return; }
        const saved = 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] = saved;
    };
    dfs(sr, sc, walk - 1);
    return ans;
}

class Solution {
    private int m, n, ans;
    private int[][] grid;

    public int uniquePathsIII(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        int sr = 0, sc = 0, walk = 1; // include start
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) { sr = r; sc = c; }
                else if (grid[r][c] == 0) walk++;
            }
        }
        ans = 0;
        dfs(sr, sc, walk - 1);
        return ans;
    }

    private void dfs(int r, int c, int remaining) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == -1) return;
        if (grid[r][c] == 2) {
            if (remaining == 0) ans++;
            return;
        }
        int saved = 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] = saved;
    }
}

function uniquePathsIII(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    let sr = 0, sc = 0, walk = 1; // include start
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 1) { sr = r; sc = c; }
            else if (grid[r][c] === 0) walk++;
        }
    }
    let ans = 0;
    const dfs = (r: number, c: number, remaining: number): void => {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] === -1) return;
        if (grid[r][c] === 2) { if (remaining === 0) ans++; return; }
        const saved = 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] = saved;
    };
    dfs(sr, sc, walk - 1);
    return ans;
}

Editorial#

The remaining counter encodes the “every cell visited” goal: when we reach the end and remaining == 0, every walkable was used. In-place mutation as visited marker; restore on backtrack.

Complexity#

Time: O(4^k) where k is the walkable count.
Space: O(k) recursion.

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#