Count Paths That Visit Every Open Cell Exactly Once
Implement countFullCoveragePaths
You're given a grid with exactly one start cell (1), exactly one end cell (2), some obstacle cells (-1), and the rest open (0). Count the number of paths from start to end, moving one step at a time horizontally or vertically and never revisiting a cell, that pass through every single open cell along the way — not just some of them.
Checking full coverage by scanning the entire grid every time the end cell is reached works, but the end cell is often reached by paths that haven't covered everything yet, and each of those arrivals pays for a full scan regardless. Counting the total number of cells that need covering once, up front, and carrying a running "how many are left" count down through the recursion turns that scan into a single number already sitting there the moment it's needed — no re-inspection of the grid required.
Example 1:
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Example 2:
Input: grid = [[1,2]]
Output: 1
Example 3:
Input: grid = [[0,1],[2,0]]
Output: 0
+ 5 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ grid.length, grid[0].length ≤ 5 - ●
Exactly one cell holds 1 (start) and exactly one holds 2 (end); -1 marks an obstacle, 0 an open walkable cell - ●
Movement is one step at a time, horizontally or vertically, never onto an obstacle and never revisiting a cell already on the current path - ●
A path only counts if it visits every non-obstacle cell exactly once before reaching the end
grid =
[[1,0,0,0], [0,0,0,0], [0,0,2,-1]]