hardBacktrackingPure DSA~30 min
Count Walks Covering Every Free Cell Once
A cleaning robot must walk from its dock to a charging pad, stepping on every walkable tile exactly once and avoiding obstacles. Count how many such complete-coverage routes exist.
Problem
Given an m x n grid where 1 is the start, 2 is the end, 0 is a walkable cell, and -1 is an obstacle, count the 4-directional paths from start to end that visit every non-obstacle cell exactly once.
Input
An m x n integer grid containing exactly one 1 and one 2.
Output
An integer: the number of complete-coverage paths.
Constraints
- 1 <= m, n <= 20 with m * n <= 20
- There is exactly one start (1) and one end (2).
Examples
Example 1
Input
grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output
2
Two distinct routes cover all walkable cells and end at 2.
Example 2
Input
grid = [[0,1],[2,0]]
Output
0
No route covers both 0 cells exactly once ending at 2.