#3797
Count Routes to Climb a Rectangular Grid
international master · 2125 · lc hard +32 · 24% accepted · 35 likes · top 3%
Description
Given an n x m string grid where '.' marks open cells and '#' marks blocked ones, count distinct routes from any open cell in the bottom row (row n-1) to any open cell in the top row (row 0), where each step moves between open cells with Euclidean distance at most d, either stays on the same row or advances one row upward, and no two consecutive steps may both stay on the same row; return the count modulo 109 + 7.
Example 1:
.2
#1
Example 2:
32
#1
Example 3:
2.
#1
Example 4:
23
#1
Example 5:
.1
Example 6:
1.
Example 7:
12
Example 8:
21
Code
1
2
3