In a grid of open cells (O) and walls (X), count the paths from the top-left to the
bottom-right cell, moving only right or down and never onto a wall. If the start
or end is a wall, the answer is 0.
countPaths(grid)
Input format: rows separated by |, each a string of O/X.
OOO|OOO|OOO // → 6
OXO|OOO|OOO // → 3
OO|XO // → 1
At any open cell, a path to the corner must go through the cell to the right or the cell below — the only two legal moves. So paths from here equal paths from the right plus paths from below.
Standing on the destination counts as one path. A move off the grid or onto a wall contributes zero.
Many different routes pass through the same cell — right-then-down and down-then-right can both reach the same intermediate cell. The naive recursion recomputes "paths from here to the end" independently for every route that arrives there, even though that count depends only on position, not history. Overlapping calls grow exponentially with grid size.
The path count from a cell depends only on its (row, column) — nothing about how you got there. Cache keyed by (row, column). Check before recursing; if cached, return it. Otherwise sum the right and down recursive results, store, return.
Only rows × cols distinct cells exist, each computed once at constant cost given its neighbors' cached values — O(rows × cols) instead of exponential.
def count_paths(grid):
rows = len(grid)
cols = len(grid[0])
memo = {}
def f(r, c):
if r >= rows or c >= cols or grid[r][c] == "X":
return 0
if r == rows - 1 and c == cols - 1:
return 1
key = (r, c)
if key in memo:
return memo[key]
v = f(r + 1, c) + f(r, c + 1)
memo[key] = v
return v
return f(0, 0)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.