3651. Minimum Cost Path with Teleportations Hard

1/**
2 * [3651] Minimum Cost Path with Teleportations
3 *
4 * You are given a m x n 2D integer array grid and an integer k. You start at the top-left cell (0, 0) and your goal is to reach the bottom‐right cell (m - 1, n - 1).
5 * There are two types of moves available:
6 * 
7 * 	
8 * 	Normal move: You can move right or down from your current cell (i, j), i.e. you can move to (i, j + 1) (right) or (i + 1, j) (down). The cost is the value of the destination cell.
9 * 	
10 * 	
11 * 	Teleportation: You can teleport from any cell (i, j), to any cell (x, y) such that grid[x][y] <= grid[i][j]; the cost of this move is 0. You may teleport at most k times.
12 * 	
13 * 
14 * Return the minimum total cost to reach cell (m - 1, n - 1) from (0, 0).
15 *  
16 * <strong class="example">Example 1:
17 * <div class="example-block">
18 * Input: <span class="example-io">grid = [[1,3,3],[2,5,4],[4,3,5]], k = 2</span>
19 * Output: <span class="example-io">7</span>
20 * Explanation:
21 * Initially we are at (0, 0) and cost is 0.
22 * <table style="border: 1px solid black;">
23 * 	<tbody>
24 * 		<tr>
25 * 			<th style="border: 1px solid black;">Current Position</th>
26 * 			<th style="border: 1px solid black;">Move</th>
27 * 			<th style="border: 1px solid black;">New Position</th>
28 * 			<th style="border: 1px solid black;">Total Cost</th>
29 * 		</tr>
30 * 		<tr>
31 * 			<td style="border: 1px solid black;">(0, 0)</td>
32 * 			<td style="border: 1px solid black;">Move Down</td>
33 * 			<td style="border: 1px solid black;">(1, 0)</td>
34 * 			<td style="border: 1px solid black;">0 + 2 = 2</td>
35 * 		</tr>
36 * 		<tr>
37 * 			<td style="border: 1px solid black;">(1, 0)</td>
38 * 			<td style="border: 1px solid black;">Move Right</td>
39 * 			<td style="border: 1px solid black;">(1, 1)</td>
40 * 			<td style="border: 1px solid black;">2 + 5 = 7</td>
41 * 		</tr>
42 * 		<tr>
43 * 			<td style="border: 1px solid black;">(1, 1)</td>
44 * 			<td style="border: 1px solid black;">Teleport to (2, 2)</td>
45 * 			<td style="border: 1px solid black;">(2, 2)</td>
46 * 			<td style="border: 1px solid black;">7 + 0 = 7</td>
47 * 		</tr>
48 * 	</tbody>
49 * </table>
50 * The minimum cost to reach bottom-right cell is 7.
51 * </div>
52 * <strong class="example">Example 2:
53 * <div class="example-block">
54 * Input: <span class="example-io">grid = [[1,2],[2,3],[3,4]], k = 1</span>
55 * Output: <span class="example-io">9</span>
56 * Explanation: 
57 * Initially we are at (0, 0) and cost is 0.
58 * <table style="border: 1px solid black;">
59 * 	<tbody>
60 * 		<tr>
61 * 			<th style="border: 1px solid black;">Current Position</th>
62 * 			<th style="border: 1px solid black;">Move</th>
63 * 			<th style="border: 1px solid black;">New Position</th>
64 * 			<th style="border: 1px solid black;">Total Cost</th>
65 * 		</tr>
66 * 		<tr>
67 * 			<td style="border: 1px solid black;">(0, 0)</td>
68 * 			<td style="border: 1px solid black;">Move Down</td>
69 * 			<td style="border: 1px solid black;">(1, 0)</td>
70 * 			<td style="border: 1px solid black;">0 + 2 = 2</td>
71 * 		</tr>
72 * 		<tr>
73 * 			<td style="border: 1px solid black;">(1, 0)</td>
74 * 			<td style="border: 1px solid black;">Move Right</td>
75 * 			<td style="border: 1px solid black;">(1, 1)</td>
76 * 			<td style="border: 1px solid black;">2 + 3 = 5</td>
77 * 		</tr>
78 * 		<tr>
79 * 			<td style="border: 1px solid black;">(1, 1)</td>
80 * 			<td style="border: 1px solid black;">Move Down</td>
81 * 			<td style="border: 1px solid black;">(2, 1)</td>
82 * 			<td style="border: 1px solid black;">5 + 4 = 9</td>
83 * 		</tr>
84 * 	</tbody>
85 * </table>
86 * The minimum cost to reach bottom-right cell is 9.
87 * </div>
88 *  
89 * Constraints:
90 * 
91 * 	2 <= m, n <= 80
92 * 	m == grid.length
93 * 	n == grid[i].length
94 * 	0 <= grid[i][j] <= 10^4
95 * 	0 <= k <= 10
96 * 
97 */
98pub struct Solution {}
99
100// problem: https://leetcode.com/problems/minimum-cost-path-with-teleportations/
101// discuss: https://leetcode.com/problems/minimum-cost-path-with-teleportations/discuss/?currentPage=1&orderBy=most_votes&query=
102
103// submission codes start here
104
105impl Solution {
106    pub fn min_cost(grid: Vec<Vec<i32>>, k: i32) -> i32 {
107        0
108    }
109}
110
111// submission codes end
112
113#[cfg(test)]
114mod tests {
115    use super::*;
116
117    #[test]
118    fn test_3651() {
119    }
120}
121