Count Paths Through a Grid Moving Only Down or Right
Implement countGridPaths
You're given a grid of open (1) and blocked (0) cells. Starting at the top-left cell and moving only down or right one step at a time, count every distinct path that reaches the bottom-right cell without ever stepping on a blocked one.
Recursively trying both directions from every cell finds every path, but the same cell gets reached by many different down/right sequences on the way to the corner, and each arrival re-explores everything reachable from that cell all over again. Remembering a cell's path count the first time it's fully computed turns every later arrival at that same cell into a single lookup — the search still considers the same set of paths, it just never re-derives a cell's contribution to them more than once.
Example 1:
Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 2
Example 2:
Input: grid = [[1,1],[1,1]]
Output: 2
Example 3:
Input: grid = [[0,1],[1,1]]
Output: 0
+ 5 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ grid.length, grid[0].length ≤ 15 - ●
Every cell holds 1 (open) or 0 (blocked) - ●
Movement is restricted to one step down or one step right at a time — no other directions are allowed - ●
A path starts at the top-left cell and ends at the bottom-right cell; if either is blocked, no path exists
grid =
[[1,1,1], [1,0,1], [1,1,1]]