1575. Count All Possible Routes Hard

1/**
2 * [1575] Count All Possible Routes
3 *
4 * You are given an array of distinct positive integers locations where locations[i] represents the position of city i. You are also given integers start, finish and fuel representing the starting city, ending city, and the initial amount of fuel you have, respectively.
5 * At each step, if you are at city i, you can pick any city j such that j != i and 0 <= j < locations.length and move to city j. Moving from city i to city j reduces the amount of fuel you have by |locations[i] - locations[j]|. Please notice that |x| denotes the absolute value of x.
6 * Notice that fuel cannot become negative at any point in time, and that you are allowed to visit any city more than once (including start and finish).
7 * Return the count of all possible routes from start to finish. Since the answer may be too large, return it modulo 10^9 + 7.
8 *  
9 * Example 1:
10 * 
11 * Input: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
12 * Output: 4
13 * Explanation: The following are all possible routes, each uses 5 units of fuel:
14 * 1 -> 3
15 * 1 -> 2 -> 3
16 * 1 -> 4 -> 3
17 * 1 -> 4 -> 2 -> 3
18 * 
19 * Example 2:
20 * 
21 * Input: locations = [4,3,1], start = 1, finish = 0, fuel = 6
22 * Output: 5
23 * Explanation: The following are all possible routes:
24 * 1 -> 0, used fuel = 1
25 * 1 -> 2 -> 0, used fuel = 5
26 * 1 -> 2 -> 1 -> 0, used fuel = 5
27 * 1 -> 0 -> 1 -> 0, used fuel = 3
28 * 1 -> 0 -> 1 -> 0 -> 1 -> 0, used fuel = 5
29 * 
30 * Example 3:
31 * 
32 * Input: locations = [5,2,1], start = 0, finish = 2, fuel = 3
33 * Output: 0
34 * Explanation: It is impossible to get from 0 to 2 using only 3 units of fuel since the shortest route needs 4 units of fuel.
35 * 
36 *  
37 * Constraints:
38 * 
39 * 	2 <= locations.length <= 100
40 * 	1 <= locations[i] <= 10^9
41 * 	All integers in locations are distinct.
42 * 	0 <= start, finish < locations.length
43 * 	1 <= fuel <= 200
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/count-all-possible-routes/
49// discuss: https://leetcode.com/problems/count-all-possible-routes/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn count_routes(locations: Vec<i32>, start: i32, finish: i32, fuel: i32) -> i32 {
55        0
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_1575() {
67    }
68}
69