Loading problem…
You are given an `m x n` integer array `grid` where `grid[i][j]` could be: - `1` representing the **starting** square. There is exactly one starting square. - `2` representing the **ending** square. There is exactly one ending square. - `0` representing empty squares we can walk over. - `-1` representing obstacles that we cannot walk over. Return the number of **4-directional** walks from the starting square to the ending square, that walk over **every non-obstacle square exactly once**.
Example 1
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: Two distinct walks cover all 11 walkable squares exactly once and finish on the end square.
Example 2
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: With no obstacle there are four full-coverage walks from start to end.
Example 3
Input: grid = [[0,1],[2,0]]
Output: 0
Explanation: From the start (1) the end (2) is diagonal; no 4-directional walk covers every square exactly once.
We need a walk from start to end that covers every walkable square exactly once — a Hamiltonian path. Count the walkable squares first, then DFS in 4 directions, marking cells visited on the way in and unmarking on the way out. Only count a route that lands on the end with zero walkable squares remaining.
Run checks all cases above. Submit evaluates all test cases.