You are given a string array grid of size n, where each string grid[i] has length m. The character grid[i][j] is one of the following symbols:
'.': The cell is available.'#': The cell is blocked.You want to count the number of different routes to climb grid. Each route must start from any cell in the bottom row (row n - 1) and end in the top row (row 0).
However, there are some constraints on the route.
d, where d is an integer parameter given to you. The Euclidean distance between two cells (r1, c1), (r2, c2) is sqrt((r1 - r2)2 + (c1 - c2)2).r to r - 1).Return an integer denoting the number of such routes. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: grid = ["..","#."], d = 1
Output: 2
Explanation:
We label the cells we visit in the routes sequentially, starting from 1. The two routes are:
.2 #1
32 #1
We can move from the cell (1, 1) to the cell (0, 1) because the Euclidean distance is sqrt((1 - 0)2 + (1 - 1)2) = sqrt(1) <= d.
However, we cannot move from the cell (1, 1) to the cell (0, 0) because the Euclidean distance is sqrt((1 - 0)2 + (1 - 0)2) = sqrt(2) > d.
Example 2:
Input: grid = ["..","#."], d = 2
Output: 4
Explanation:
Two of the routes are given in example 1. The other two routes are:
2. #1
23 #1
Note that we can move from (1, 1) to (0, 0) because the Euclidean distance is sqrt(2) <= d.
Example 3:
Input: grid = ["#"], d = 750
Output: 0
Explanation:
We cannot choose any cell as the starting cell. Therefore, there are no routes.
Example 4:
Input: grid = [".."], d = 1
Output: 4
Explanation:
The possible routes are:
.1
1.
12
21
Constraints:
1 <= n == grid.length <= 7501 <= m == grid[i].length <= 750grid[i][j] is '.' or '#'.1 <= d <= 750Solutions for this problem are being prepared.
Try solving it yourselfPractice Count Routes to Climb a Rectangular Grid with our built-in code editor and test cases.
Practice on FleetCode