3603. Minimum Cost Path with Alternating Directions II Medium

1/**
2 * [3603] Minimum Cost Path with Alternating Directions II
3 *
4 * You are given two integers m and n representing the number of rows and columns of a grid, respectively.
5 * The cost to enter cell (i, j) is defined as (i + 1) * (j + 1).
6 * You are also given a 2D integer array waitCost where waitCost[i][j] defines the cost to wait on that cell.
7 * The path will always begin by entering cell (0, 0) on move 1 and paying the entrance cost.
8 * At each step, you follow an alternating pattern:
9 * 
10 * 	On odd-numbered seconds, you must move right or down to an adjacent cell, paying its entry cost.
11 * 	On even-numbered seconds, you must wait in place for exactly one second and pay waitCost[i][j] during that second.
12 * 
13 * Return the minimum total cost required to reach (m - 1, n - 1).
14 *  
15 * <strong class="example">Example 1:
16 * <div class="example-block">
17 * Input: <span class="example-io">m = 1, n = 2, waitCost = [[1,2]]</span>
18 * Output: <span class="example-io">3</span>
19 * Explanation:
20 * The optimal path is:
21 * 
22 * 	Start at cell (0, 0) at second 1 with entry cost (0 + 1) * (0 + 1) = 1.
23 * 	Second 1: Move right to cell (0, 1) with entry cost (0 + 1) * (1 + 1) = 2.
24 * 
25 * Thus, the total cost is 1 + 2 = 3.
26 * </div>
27 * <strong class="example">Example 2:
28 * <div class="example-block">
29 * Input: <span class="example-io">m = 2, n = 2, waitCost = [[3,5],[2,4]]</span>
30 * Output: <span class="example-io">9</span>
31 * Explanation:
32 * The optimal path is:
33 * 
34 * 	Start at cell (0, 0) at second 1 with entry cost (0 + 1) * (0 + 1) = 1.
35 * 	Second 1: Move down to cell (1, 0) with entry cost (1 + 1) * (0 + 1) = 2.
36 * 	Second 2: Wait at cell (1, 0), paying waitCost[1][0] = 2.
37 * 	Second 3: Move right to cell (1, 1) with entry cost (1 + 1) * (1 + 1) = 4.
38 * 
39 * Thus, the total cost is 1 + 2 + 2 + 4 = 9.
40 * </div>
41 * <strong class="example">Example 3:
42 * <div class="example-block">
43 * Input: <span class="example-io">m = 2, n = 3, waitCost = [[6,1,4],[3,2,5]]</span>
44 * Output: <span class="example-io">16</span>
45 * Explanation:
46 * The optimal path is:
47 * 
48 * 	Start at cell (0, 0) at second 1 with entry cost (0 + 1) * (0 + 1) = 1.
49 * 	Second 1: Move right to cell (0, 1) with entry cost (0 + 1) * (1 + 1) = 2.
50 * 	Second 2: Wait at cell (0, 1), paying waitCost[0][1] = 1.
51 * 	Second 3: Move down to cell (1, 1) with entry cost (1 + 1) * (1 + 1) = 4.
52 * 	Second 4: Wait at cell (1, 1), paying waitCost[1][1] = 2.
53 * 	Second 5: Move right to cell (1, 2) with entry cost (1 + 1) * (2 + 1) = 6.
54 * 
55 * Thus, the total cost is 1 + 2 + 1 + 4 + 2 + 6 = 16.
56 * </div>
57 *  
58 * Constraints:
59 * 
60 * 	1 <= m, n <= 10^5
61 * 	2 <= m * n <= 10^5
62 * 	waitCost.length == m
63 * 	waitCost[0].length == n
64 * 	0 <= waitCost[i][j] <= 10^5
65 * 
66 */
67pub struct Solution {}
68
69// problem: https://leetcode.com/problems/minimum-cost-path-with-alternating-directions-ii/
70// discuss: https://leetcode.com/problems/minimum-cost-path-with-alternating-directions-ii/discuss/?currentPage=1&orderBy=most_votes&query=
71
72// submission codes start here
73
74impl Solution {
75    pub fn min_cost(m: i32, n: i32, wait_cost: Vec<Vec<i32>>) -> i64 {
76        
77    }
78}
79
80// submission codes end
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85
86    #[test]
87    fn test_3603() {
88    }
89}
90