Enumerate all 4-directional walks from Start (1) to End (2) that step over every single non-obstacle cell exactly once. Precompute total visitable cells and verify remain == 0 at the destination.
2 is successful IF AND ONLY IF remain == 0. Reaching 2 prematurely with remain > 0 discards the walk as invalid.
"Before executing DFS, we perform an $O(mn)$ scan to locate the start square (1) and count all visitable cells (each 0 plus the starting cell). This count determines our exact coverage requirement."
"When our DFS reaches cell value 2, we return 1 if and only if remain == 0. If remain > 0, we arrived at the goal prematurely leaving cells unvisited, which is an invalid walk."
"We mutate grid[r][c] = -2 to mark cell as visited, decrement remain--, recurse in 4 directions, and strictly restore grid[r][c] = 0 and remain++ during unwind."
"Finding Hamiltonian paths is NP-complete in general, but here $m \times n \le 20$. At each step, we branch in at most 3 directions (excluding parent), giving $O(3^{mn})$ worst-case time with aggressive obstacle pruning."