Enumerate Top-to-Bottom Grid Paths

You are given a rectangular binary matrix grid. A cell with value 0 is open, and a cell with value 1 is blocked.
A path may start at any open cell in the top row. At each step, it may move one cell down, right, left, or up, staying inside the matrix and entering only open cells. A path is simple: it may not visit the same cell more than once. The path ends immediately when it first reaches the bottom row.
Return every distinct valid path. Represent a cell as [row, column] and a path as its ordered list of cells.
Return paths in deterministic depth-first-search order:
Consider top-row starting cells from left to right.
From each cell, try neighbors in the order down, right, left, then up.

Function
enumerateTopToBottomPaths(grid: int[][]) → int[][][]

Examples
Example 1
grid = [[0,0],[0,0]]
return = [[[0,0],[1,0]],[[0,0],[0,1],[1,1]],[[0,1],[1,1]],[[0,1],[0,0],[1,0]]]
Both top-row cells are valid starts. Depth-first search uses down, right, left, then up, and stops each path as soon as it reaches row 1.
Example 2
grid = [[0,1],[1,1]]
return = []
The only open top-row cell has no open route to the bottom row, so there are no valid paths.
Example 3
grid = [[0,1,0]]
return = [[[0,0]],[[0,2]]]
In a one-row matrix, every open top-row cell is already in the bottom row. Starts are returned from left to right.

Constraints
1 <= grid.length <= 6
1 <= grid[i].length <= 6
Every row has the same length.
Every cell is either 0 or 1.
There are at most 16 open cells.
The input has at most 10000 valid paths.
A path may not repeat a cell and ends on its first bottom-row cell.

The trick is that this is enumeration, not search for a shortest path, so BFS is the wrong instinct even though the hint says it. Use recursive DFS with a visited set and a current path list. Push the cell, mark it visited, and if its row is the last row, copy the path into results and return immediately. Otherwise try neighbors in the exact order down, right, left, up. Then unmark and pop on the way back. The common pitfalls are forgetting to copy the path before storing it, continuing past the bottom row, and getting direction order wrong, which scrambles the output. A one-row grid is the edge case: every open top cell is already a finished path. With at most 10000 valid paths, complexity is fine. If you blank on the backtrack cleanup during the live OA, StealthCoder can hand you the clean version.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.