A grid is given as a list of equal-length strings: "." is open and "#" is a rock. You start in the top-left cell and want to reach the bottom-right cell, moving only right or down, and never onto a rock.
Implement count_paths(grid: list[str]) -> int: the number of different routes.
count_paths([
"...",
".#.",
"...",
]) # 2 around the rock on the right or on the left
count_paths(["..#.", "...."]) # 2 you must step down before reaching the rock
If the start or the finish is a rock, the answer is 0. A 1 x 1 open grid has exactly 1 route (you're already there).
Constraints: grids are 1 to 100 cells on each side. Python ints don't overflow, so return the exact count, which can be huge.
Show hint
ways[r][c] is 0 on a rock and otherwise ways[r-1][c] + ways[r][c-1] (treating cells outside the grid as 0), with ways[0][0] = 1; the first row and column are not all 1s once a rock blocks them.