576. Unique Paths III
You are given a rectangular grid grid where each cell holds one of four codes: 1 marks the starting square (there is exactly one), 2 marks the ending square (exactly one), 0 is an open square you may walk on, and -1 is a blocked square you may never enter.
From any square you may step up, down, left, or right — never diagonally, never off the grid. Count the walks that begin on the start square, finish on the end square, and step on every non-blocked square exactly once along the way (the start and end squares included). Return that count as an integer.
Because every open square must be covered, this is a Hamiltonian-path count on the grid — the total cell count is small, which is your license to search exhaustively.
Example 1:
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: Two full-coverage walks exist. One sweeps the top row right, drops down the right side, sweeps left, then covers the bottom row to the 2; the other goes down the left edge first and snakes back. Both touch all 11 open squares once.
Example 2:
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: With the corner unblocked there are four ways to snake through all 12 squares.
Example 3:
Input: grid = [[0,1],[2,0]]
Output: 0
Explanation: Any walk from the 1 to the 2 covers at most three of the four squares, so no walk covers everything.
Constraints:
- 1 ≤ m, n ≤ 20
- 1 ≤ m * n ≤ 20
- grid[i][j] is 1, 2, 0, or -1
- There is exactly one start square (1) and exactly one end square (2)
Hints:
First count how many squares must be visited: every cell that is not -1. A valid walk arrives at the 2 with exactly that many squares consumed.
Depth-first search with undo: mark the current square used, recurse into the four neighbors, then unmark it on the way back so sibling branches see a clean grid.
With at most 20 cells you can also encode the visited set as a bitmask and memoize (position, mask) — identical states reached in different orders then share one computed answer.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Expected output: 2