Unique Paths III

hard array backtracking matrix

Problem

Grid contains 1 (start), 2 (end), 0 (empty), -1 (wall). Return the number of distinct 4-directional walks from start to end that visit every empty square exactly once.

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

Output2

Backtrack. Track remaining empties; only count when we land on end with 0 remaining.

grid (rows by ';')

def uniquePathsIII(grid):
    R, C = len(grid), len(grid[0])
    sr = sc = empty = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 1: sr, sc = r, c
            if grid[r][c] != -1: empty += 1
    count = 0
    def dfs(r, c, left):
        nonlocal count
        if grid[r][c] == 2:
            if left == 0: count += 1
            return
        save = grid[r][c]; grid[r][c] = -1
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != -1:
                dfs(nr, nc, left - 1)
        grid[r][c] = save
    dfs(sr, sc, empty - 1)
    return count

function uniquePathsIII(grid) {
  const R = grid.length, C = grid[0].length;
  let sr = 0, sc = 0, empty = 0;
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) {
    if (grid[r][c] === 1) { sr = r; sc = c; }
    if (grid[r][c] !== -1) empty++;
  }
  let count = 0;
  function dfs(r, c, left) {
    if (grid[r][c] === 2) { if (left === 0) count++; return; }
    const save = grid[r][c]; grid[r][c] = -1;
    for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] !== -1) dfs(nr, nc, left - 1);
    }
    grid[r][c] = save;
  }
  dfs(sr, sc, empty - 1);
  return count;
}

class Solution {
    int R, C, count = 0;
    int[][] g;
    public int uniquePathsIII(int[][] grid) {
        g = grid; R = grid.length; C = grid[0].length;
        int sr = 0, sc = 0, empty = 0;
        for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) {
            if (g[r][c] == 1) { sr = r; sc = c; }
            if (g[r][c] != -1) empty++;
        }
        dfs(sr, sc, empty - 1);
        return count;
    }
    void dfs(int r, int c, int left) {
        if (g[r][c] == 2) { if (left == 0) count++; return; }
        int save = g[r][c]; g[r][c] = -1;
        int[][] D = { {1,0},{-1,0},{0,1},{0,-1} };
        for (int[] dd : D) {
            int nr = r + dd[0], nc = c + dd[1];
            if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] != -1) dfs(nr, nc, left - 1);
        }
        g[r][c] = save;
    }
}

int uniquePathsIII(vector<vector<int>>& grid) {
    int R = (int)grid.size(), C = (int)grid[0].size();
    int sr = 0, sc = 0, empty = 0;
    for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) {
        if (grid[r][c] == 1) { sr = r; sc = c; }
        if (grid[r][c] != -1) empty++;
    }
    int count = 0;
    function<void(int, int, int)> dfs = [&](int r, int c, int left) {
        if (grid[r][c] == 2) { if (left == 0) count++; return; }
        int save = grid[r][c]; grid[r][c] = -1;
        int D[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
        for (auto& dd : D) {
            int nr = r + dd[0], nc = c + dd[1];
            if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] != -1) dfs(nr, nc, left - 1);
        }
        grid[r][c] = save;
    };
    dfs(sr, sc, empty - 1);
    return count;
}

Explanation

We must count walks from the start cell to the end cell that step through every empty square exactly once. The clean way to do this is backtracking: try every direction, mark cells as we go, and undo the marks when we back out.

First we scan the grid to find the start position and count how many cells are actually walkable (everything that isn't a wall -1). We track this as left — the number of squares still to visit.

The dfs(r, c, left) function temporarily turns the current cell into a wall (grid[r][c] = -1) so we can't revisit it, then recurses into the four neighbours with left - 1. After exploring, it restores the cell with grid[r][c] = save so other paths can still use it.

The counting rule is strict: we only increment count when we land on the end cell (value 2) and left == 0, meaning we have used up every empty square. Reaching the end early with squares still unvisited does not count.

Example: in the sample 3 × 4 grid there are exactly 2 such full-coverage walks from start to end, so the answer is 2.

Time: O(3ᵏ) where k = empties Space: O(k)