623. Visit Every Square
A robot vacuum must clean a floor plan drawn as the matrix grid. A cell with 0 is blocked by furniture, a cell with 1 is an open square, 2 is the dock where the robot starts and 3 is the charger where it must finish. There is exactly one dock and exactly one charger.
The robot moves one step at a time to a neighbouring cell (up, down, left or right) that is not blocked, and it may never enter the same cell twice. A route is complete when it starts at the dock, ends at the charger and has stepped on every non-blocked cell exactly once. Return the number of complete routes.
Example 1
- Input:
- grid = [[2,1,1],[1,1,3]]
- Output:
- 1
- Explanation:
One route covers all six open cells: down, right, up, right, down, with the charger last.
Example 2
- Input:
- grid = [[2,3,0],[1,1,1]]
- Output:
- 0
- Explanation:
The charger sits next to the dock, so any route that reaches it early leaves cells unvisited: no complete route exists.
Example 3
- Input:
- grid = [[2,1,1],[1,1,1],[1,1,3]]
- Output:
- 2
- Explanation:
Two different snaking routes cover all nine cells of the 3 x 3 floor and end at the charger.
Constraints
- 1 ≤
grid.length,grid[i].length≤ 5 - Each entry of
gridis 0, 1, 2 or 3. - Exactly one cell is 2 and exactly one cell is 3.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(3^(m*n))
- Space
- O(m*n)