Code Implementation

class Solution:
    def uniquePathsIII(self, grid):
        rows, cols = len(grid), len(grid[0])
        empty = 1  # Start square counts as empty
        sx = sy = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 0:
                    empty += 1
                elif grid[i][j] == 1:
                    sx, sy = i, j

        self.ans = 0

        def dfs(x, y, remain):
            if x < 0 or x >= rows or y < 0 or y >= cols or grid[x][y] == -1:
                return
            if grid[x][y] == 2:
                if remain == 0:
                    self.ans += 1
                return
            temp = grid[x][y]
            grid[x][y] = -1
            for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                dfs(x+dx, y+dy, remain-1)
            grid[x][y] = temp

        dfs(sx, sy, empty)
        return self.ans
      

class Solution {
public:
    int ans = 0;
    int uniquePathsIII(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        int empty = 1, sx = 0, sy = 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) { sx = i; sy = j; }
            }
        }
        dfs(grid, sx, sy, empty);
        return ans;
    }
    void dfs(vector<vector<int>>& grid, int x, int y, int remain) {
        int rows = grid.size(), cols = grid[0].size();
        if (x < 0 || x >= rows || y < 0 || y >= cols || grid[x][y] == -1)
            return;
        if (grid[x][y] == 2) {
            if (remain == 0) ans++;
            return;
        }
        int temp = grid[x][y];
        grid[x][y] = -1;
        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        for (auto& d : dirs)
            dfs(grid, x+d[0], y+d[1], remain-1);
        grid[x][y] = temp;
    }
};
      

class Solution {
    private int ans = 0;
    public int uniquePathsIII(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int empty = 1, sx = 0, sy = 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) { sx = i; sy = j; }
            }
        }
        dfs(grid, sx, sy, empty);
        return ans;
    }
    private void dfs(int[][] grid, int x, int y, int remain) {
        int rows = grid.length, cols = grid[0].length;
        if (x < 0 || x >= rows || y < 0 || y >= cols || grid[x][y] == -1)
            return;
        if (grid[x][y] == 2) {
            if (remain == 0) ans++;
            return;
        }
        int temp = grid[x][y];
        grid[x][y] = -1;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int[] d : dirs)
            dfs(grid, x+d[0], y+d[1], remain-1);
        grid[x][y] = temp;
    }
}
      

var uniquePathsIII = function(grid) {
    let rows = grid.length, cols = grid[0].length;
    let empty = 1, sx = 0, sy = 0;
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === 0) empty++;
            else if (grid[i][j] === 1) { sx = i; sy = j; }
        }
    }
    let ans = 0;
    function dfs(x, y, remain) {
        if (x < 0 || x >= rows || y < 0 || y >= cols || grid[x][y] === -1)
            return;
        if (grid[x][y] === 2) {
            if (remain === 0) ans++;
            return;
        }
        let temp = grid[x][y];
        grid[x][y] = -1;
        let dirs = [[-1,0],[1,0],[0,-1],[0,1]];
        for (let [dx, dy] of dirs)
            dfs(x+dx, y+dy, remain-1);
        grid[x][y] = temp;
    }
    dfs(sx, sy, empty);
    return ans;
};
      

Problem Description

The Unique Paths III problem asks you to find the number of unique paths from a given starting square to an ending square in a 2D grid. The grid contains four types of cells:

• 1: The starting square (exactly one in the grid)
• 2: The ending square (exactly one in the grid)
• 0: Empty squares you can walk over
• -1: Obstacles you cannot walk over

• You can move up, down, left, or right (not diagonally).
• You must start at the square with 1 and end at the square with 2.
• You must walk over every empty square (0) exactly once. You cannot walk over obstacles or revisit any square.
• The path must visit all non-obstacle squares (0 and 1 and 2) exactly once.

Thought Process

At first glance, this problem seems similar to a classic pathfinding problem, such as finding a path from start to end. However, the key twist is that you must visit every empty square exactly once, without revisiting or skipping any. This is similar to finding a Hamiltonian path in a grid, which is generally a hard computational problem.

A brute-force approach would be to try every possible path from the start to the end, checking if all empty squares are covered. However, this quickly becomes infeasible as the grid size increases, due to the exponential number of possible paths.

To optimize, we can use Depth-First Search (DFS) with backtracking. The idea is to recursively explore all possible moves, marking squares as visited and backtracking when necessary. We keep track of the number of squares left to visit, and only count a path as valid if it ends at the finish square with all empty squares visited.

Solution Approach

We can solve this problem step-by-step as follows:

1. Find the starting point and count empty squares:
   • Scan the grid to locate the cell with 1 (the start), and count the total number of empty cells (0). We also need to include the starting square as a square to visit.
2. Use DFS with backtracking:
   • From the starting point, recursively try moving in all four directions (up, down, left, right).
   • If the next cell is an obstacle or already visited, skip it.
   • Mark the cell as visited before moving, and unmark (backtrack) after exploring all options from that cell.
3. Base cases:
   • If we reach the ending square (2) and have visited all empty squares (tracked by a counter), we count it as a valid path.
   • If we run out of squares to visit or hit an obstacle, we return without incrementing the path count.
4. Return the answer:
   • The total number of valid paths found is returned as the answer.

We use in-place marking (e.g., setting the cell to -1) to track visited cells, and backtrack to restore them after the recursive call. This avoids the need for an extra visited matrix.

Example Walkthrough

Let's consider the following grid:

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

• The starting square is at (0,0).
• The ending square is at (2,2).
• There are 8 empty squares to cover (including the start and end).

• It marks the current square as visited.
• Moves to a neighboring cell if it is not an obstacle or already visited.
• Decrements the count of remaining squares to visit.
• If it reaches (2,2) with remaining count 0, it counts as a valid path.

Time and Space Complexity

Brute-force approach:

• Time complexity: Exponential, O(4^N), where N is the number of empty squares, because each step can branch up to 4 ways.
• Space complexity: O(N) for recursion stack and visited status.

• Time complexity: Still O(4^N) in the worst case, but pruning (skipping obstacles and visited cells) makes it much faster in practice.
• Space complexity: O(N) for the recursion stack (N = number of empty squares).

Summary

The Unique Paths III problem is a classic example of using DFS with backtracking to explore all possible paths under tight constraints (must visit all empty squares exactly once). The key insights are:

• Track the number of squares left to visit so you know when a path is valid.
• Use in-place marking for visited cells to save space and simplify logic.
• Backtrack to explore all possible options efficiently.