Count Start-to-End Walks That Visit Every Traversable Grid Cell Once
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
In `grid`,1 marks the unique start,2 the unique finish,0 an ordinary traversable cell, and-1 an obstacle. Count four-directional walks from start to finish that visit every non-obstacle cell exactly once, including both endpoints.
```cpp
class Solution {
public:
int uniquePathsIII(vector<vector<int>>& grid);
};
```
### Examples
**Example 1:**
```text
Input: grid = [[1,0,2]]
Output: 1
Explanation: The only valid walk crosses the middle cell and then finishes.
```
**Example 2:**
```text
Input: grid = [[1,0],[0,2]]
Output: 0
Explanation: Both endpoint colors match on a checkerboard, but a walk using four cells has three steps and must end on the opposite color.
```
### Constraints
- `m == grid.length`, `n == grid[i].length`.
- `1 <= m,n <= 20`, and `1 <= m*n <= 20`.
- Entries are-1,0,1,or2.
- Exactly one starting cell and one ending cell exist.
### Contract considerations
The start and finish may be anywhere. Count all legal walks; do not return an arbitrary one or merely test reachability.
```hint Read the boundary condition
Arriving at the finish is valid only after every other traversable cell has been used.
```
### Boundary reminders
The start and finish may be anywhere. Count all legal walks; do not return an arbitrary one or merely test reachability.
Overview: Count Start-to-End Walks That Visit Every Traversable Grid Cell Once. In grid,1 marks the unique start,2 the unique finish,0 an ordinary traversable cell, and-1 an obstacle.
