3797. Count Routes to Climb a Rectangular Grid Hard

1/**
2 * [3797] Count Routes to Climb a Rectangular Grid
3 *
4 * 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:
5 * 
6 * 	'.': The cell is available.
7 * 	'#': The cell is blocked.
8 * 
9 * 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).
10 * However, there are some constraints on the route.
11 * 
12 * 	You can only move from one available cell to another available cell.
13 * 	The Euclidean distance of each move is at most 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).
14 * 	Each move either stays on the same row or moves to the row directly above (from row r to r - 1).
15 * 	You cannot stay on the same row for two consecutive turns. If you stay on the same row in a move (and this move is not the last move), your next move must go to the row above.
16 * 
17 * Return an integer denoting the number of such routes. Since the answer may be very large, return it modulo 10^9 + 7.
18 *  
19 * <strong class="example">Example 1:
20 * <div class="example-block">
21 * Input: <span class="example-io">grid = ["..","#."], d = 1</span>
22 * Output: <span class="example-io">2</span>
23 * Explanation:
24 * We label the cells we visit in the routes sequentially, starting from 1. The two routes are:
25 * 
26 * .2
27 * #1
28 * 
29 * 32
30 * #1
31 * 
32 * 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.
33 * 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.
34 * </div>
35 * <strong class="example">Example 2:
36 * <div class="example-block">
37 * Input: <span class="example-io">grid = ["..","#."], d = 2</span>
38 * Output: <span class="example-io">4</span>
39 * Explanation:
40 * Two of the routes are given in example 1. The other two routes are:
41 * 
42 * 2.
43 * #1
44 * 
45 * 23
46 * #1
47 * 
48 * Note that we can move from (1, 1) to (0, 0) because the Euclidean distance is sqrt(2) <= d.
49 * </div>
50 * <strong class="example">Example 3:
51 * <div class="example-block">
52 * Input: <span class="example-io">grid = ["#"], d = 750</span>
53 * Output: <span class="example-io">0</span>
54 * Explanation:
55 * We cannot choose any cell as the starting cell. Therefore, there are no routes.
56 * </div>
57 * <strong class="example">Example 4:
58 * <div class="example-block">
59 * Input: <span class="example-io">grid = [".."], d = 1</span>
60 * Output: <span class="example-io">4</span>
61 * Explanation:
62 * The possible routes are:
63 * 
64 * .1
65 * 
66 * 1.
67 * 
68 * 12
69 * 
70 * 21
71 * </div>
72 *  
73 * Constraints:
74 * 
75 * 	1 <= n == grid.length <= 750
76 * 	1 <= m == grid[i].length <= 750
77 * 	grid[i][j] is '.' or '#'.
78 * 	1 <= d <= 750
79 * 
80 */
81pub struct Solution {}
82
83// problem: https://leetcode.com/problems/count-routes-to-climb-a-rectangular-grid/
84// discuss: https://leetcode.com/problems/count-routes-to-climb-a-rectangular-grid/discuss/?currentPage=1&orderBy=most_votes&query=
85
86// submission codes start here
87
88impl Solution {
89    pub fn number_of_routes(grid: Vec<String>, d: i32) -> i32 {
90        0
91    }
92}
93
94// submission codes end
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99
100    #[test]
101    fn test_3797() {
102    }
103}
104