319. Unique Paths III

We need a walk from start to end that covers every walkable square exactly once — a Hamiltonian path. Count the walkable squares first, then DFS in 4 directions, marking cells visited on the way in and unmarking on the way out. Only count a route that lands on the end with zero walkable squares remaining.

It's a Hamiltonian path count

The route must step on every non-obstacle square exactly once and finish on the end square. So first count how many squares must be covered: all 0s plus the start and end. Track that as remaining steps.

DFS with backtracking

From the start, try all four neighbors. Mark a cell as visited (temporarily set it to an obstacle) as you enter, and restore it as you leave so other branches can use it:

dfs(r, c, remaining):
    if out of bounds or grid[r][c] == -1: return         # wall / already used
    if grid[r][c] == 2:                                   # reached the end
        if remaining == 0: count += 1                    # ...and covered everything
        return
    temp = grid[r][c]; grid[r][c] = -1                   # mark visited
    for each of the 4 directions: dfs(nr, nc, remaining - 1)
    grid[r][c] = temp                                    # un-mark (backtrack)

Start the search with remaining = (number of walkable squares) counting the start step, so reaching the end with remaining == 0 means every square was used exactly once.

Worked example

1 0 0 0
0 0 0 0
0 0 2 -1

There are 11 walkable squares. Two distinct full-coverage walks reach the 2:

1. down, down, right, right, up, up, right, right, down, down
2. right, right, right, down, left, left, down, right, right

So the answer is 2.

Complexity

• Time: O(4^(m·n)) worst case (bounded hard by m·n <= 20).
• Space: O(m·n) recursion depth.

class Solution {
    private int rows, cols, count;

    public int uniquePathsIII(int[][] grid) {
        rows = grid.length;
        cols = grid[0].length;
        int empty = 0, sr = 0, sc = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 0) empty++;
                else if (grid[i][j] == 1) { sr = i; sc = j; }
            }
        }
        count = 0;
        // remaining counts the start step too: empty squares + the start.
        dfs(grid, sr, sc, empty + 1);
        return count;
    }

    private void dfs(int[][] grid, int i, int j, int remaining) {
        if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == -1) return;
        if (grid[i][j] == 2) {
            if (remaining == 0) count++;
            return;
        }
        int temp = grid[i][j];
        grid[i][j] = -1;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int[] d : dirs) {
            dfs(grid, i + d[0], j + d[1], remaining - 1);
        }
        grid[i][j] = temp;
    }
}