Enumerate Top-to-Bottom Grid Paths
Learn this problem
GoogleFULLTIMEONSITE INTERVIEWProblem statement
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 <= 61 <= grid[i].length <= 6- Every row has the same length.
- Every cell is either
0or1. - There are at most
16open cells. - The input has at most
10000valid paths. - A path may not repeat a cell and ends on its first bottom-row cell.