DSA problem
Unique Paths III
You are given an m x n integer grid grid where each cell holds one of the values 0 (empty cell), 1 (starting square — appears exactly once), 2 (ending square — appears exactly once), or -1 (obstacle that cannot be visited). Return the number of 4-directional walks from the starting square to the ending square that walk over every non-obstacle cell exactly once.
In other words, we want Hamiltonian-style paths on the sub-graph induced by the non-obstacle cells, restricted to the four cardinal moves (up/down/left/right). Because the path must cover every walkable cell exactly once, this is fundamentally an NP-hard problem in the general case, but the constraint m * n <= 20 keeps the state space small enough that exhaustive backtracking with smart pruning is practical.
The approach has two phases. First, scan the grid to count the number of empty cells (cells with value 0 or 1 — the start counts as walkable too), and find the start position. Let empty be that count of cells that must be touched (we will use empty + 1 if we also include the start, depending on whether you count it; the cleanest invariant is "number of walkable cells", which I'll call need).
Second, run a DFS with backtracking from the start. Maintain a counter of how many cells have been visited along the current path. At each step, mark the current cell visited (e.g., by overwriting it with -1), recurse into each of the four neighbors that is in bounds and unvisited, then restore the cell on the way out. When we step onto the ending cell, increment the answer only if the visited counter equals the total number of walkable cells; otherwise we have not yet covered everything. Time is exponential in the worst case but bounded by the constraint.
Examples
grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]2grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]4grid = [[0,1],[2,0]]0Constraints
- 1 <= m, n <= 20
- 1 <= m * n <= 20
- Each cell of grid is one of -1, 0, 1, or 2.
- There is exactly one starting cell (value 1) and exactly one ending cell (value 2).
- The path must traverse every non-obstacle cell exactly once.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.