Course4all
Join us on telegram
Home/dsa/Backtracking/Unique Paths III

Unique Paths III

Master this topic with zero to advance depth.

Unique Paths III

The Grid Coverage Problem

Find the number of paths from the starting square to the ending square that walk over every non-obstacle square exactly once.

Backtracking with Path Counting

  1. Count the total number of empty squares (NN).
  2. DFS from the start, marking cells as visited (-1).
  3. If we reach the end and our current path length equals N+1N+1 (including the target), we found a valid path.

Find the number of paths in a grid that visit every empty square exactly once. Includes visual grid-coverage trace.

Hard

Examples

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Approach 1

Level I: Backtracking (DFS)

Intuition

Try all possible paths from start to end, counting steps taken.

Iterate through the grid to find the start and count empty cells. DFS in 4 directions. If we reach '2' and steps == totalEmpty, increment count.

⏱ O(3^{M * N})💾 O(M * N)

Detailed Dry Run

Trace for 1x3: [1, 0, 2] 1. Start at (0,0), empty=2. 2. Move to (0,1), steps=1. Mark visited. 3. Move to (0,2), steps=2. Target reached! Count++
java
class Solution {
    int res = 0, empty = 1, startX, startY;
    public int uniquePathsIII(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) empty++;
                else if (grid[i][j] == 1) {
                    startX = i; startY = j;
                }
            }
        }
        dfs(grid, startX, startY, 0);
        return res;
    }
    public void dfs(int[][] grid, int x, int y, int count) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == -1) return;
        if (grid[x][y] == 2) {
            if (count == empty) res++;
            return;
        }
        grid[x][y] = -1;
        dfs(grid, x + 1, y, count + 1);
        dfs(grid, x - 1, y, count + 1);
        dfs(grid, x, y + 1, count + 1);
        dfs(grid, x, y - 1, count + 1);
        grid[x][y] = 0;
    }
}
← Previous QuestionBeautiful Arrangement
Next Question →Hamiltonian Path