A forager crosses a field drawn as a list of equal-length strings: "." is open grass, "m" is a patch with a mushroom, and "#" is a boulder. She starts in the top-left cell, finishes in the bottom-right cell, moves only right or down, and never steps on a boulder. She picks the mushroom on every "m" cell she steps on, including the start and finish cells.
Her basket holds exactly k mushrooms and she wants it full, no more and no less. Implement count_walks(grid: list[str], k: int) -> int: the number of different routes that pick exactly k mushrooms.
count_walks([
"m..",
".m.",
"..m",
], 2) # 2 all 6 routes pick both corner mushrooms; the 4 that pass the centre
# pick 3, so 2 routes pick exactly 2
count_walks(["..",
"m."], 0) # 1 right, then down
If the start or the finish is a boulder, the answer is 0.
Constraints: grids are 1 to 40 cells on each side, 0 <= k <= 80. Return the exact count, which can be huge (Python ints don't overflow). Listing every route is hopeless on a 40 x 40 field.
Show hint
counting routes to each cell isn't enough any more, so add the haul to the state: ways[r][c][j] = routes from the start to (r, c) that have picked exactly j mushrooms so far. It is the sum of ways[r-1][c][j - here] and ways[r][c-1][j - here], where here is 1 on a mushroom cell and 0 otherwise.