3742. Maximum Path Score in a Grid Medium

1/**
2 * [3742] Maximum Path Score in a Grid
3 *
4 * You are given an m x n grid where each cell contains one of the values 0, 1, or 2. You are also given an integer k.
5 * You start from the top-left corner (0, 0) and want to reach the bottom-right corner (m - 1, n - 1) by moving only right or down.
6 * Each cell contributes a specific score and incurs an associated cost, according to their cell values:
7 * 
8 * 	0: adds 0 to your score and costs 0.
9 * 	1: adds 1 to your score and costs 1.
10 * 	2: adds 2 to your score and costs 1. ​​​​​​​
11 * 
12 * Return the maximum score achievable without exceeding a total cost of k, or -1 if no valid path exists.
13 * Note: If you reach the last cell but the total cost exceeds k, the path is invalid.
14 *  
15 * <strong class="example">Example 1:
16 * <div class="example-block">
17 * Input: <span class="example-io">grid = [[0, 1],[2, 0]], k = 1</span>
18 * Output: <span class="example-io">2</span>
19 * Explanation:​​​​​​​
20 * The optimal path is:
21 * <table style="border: 1px solid black;">
22 * 	<thead>
23 * 		<tr>
24 * 			<th style="border: 1px solid black;">Cell</th>
25 * 			<th style="border: 1px solid black;">grid[i][j]</th>
26 * 			<th style="border: 1px solid black;">Score</th>
27 * 			<th style="border: 1px solid black;">Total<br />
28 * 			Score</th>
29 * 			<th style="border: 1px solid black;">Cost</th>
30 * 			<th style="border: 1px solid black;">Total<br />
31 * 			Cost</th>
32 * 		</tr>
33 * 	</thead>
34 * 	<tbody>
35 * 		<tr>
36 * 			<td style="border: 1px solid black;">(0, 0)</td>
37 * 			<td style="border: 1px solid black;">0</td>
38 * 			<td style="border: 1px solid black;">0</td>
39 * 			<td style="border: 1px solid black;">0</td>
40 * 			<td style="border: 1px solid black;">0</td>
41 * 			<td style="border: 1px solid black;">0</td>
42 * 		</tr>
43 * 		<tr>
44 * 			<td style="border: 1px solid black;">(1, 0)</td>
45 * 			<td style="border: 1px solid black;">2</td>
46 * 			<td style="border: 1px solid black;">2</td>
47 * 			<td style="border: 1px solid black;">2</td>
48 * 			<td style="border: 1px solid black;">1</td>
49 * 			<td style="border: 1px solid black;">1</td>
50 * 		</tr>
51 * 		<tr>
52 * 			<td style="border: 1px solid black;">(1, 1)</td>
53 * 			<td style="border: 1px solid black;">0</td>
54 * 			<td style="border: 1px solid black;">0</td>
55 * 			<td style="border: 1px solid black;">2</td>
56 * 			<td style="border: 1px solid black;">0</td>
57 * 			<td style="border: 1px solid black;">1</td>
58 * 		</tr>
59 * 	</tbody>
60 * </table>
61 * Thus, the maximum possible score is 2.
62 * </div>
63 * <strong class="example">Example 2:
64 * <div class="example-block">
65 * Input: <span class="example-io">grid = [[0, 1],[1, 2]], k = 1</span>
66 * Output: <span class="example-io">-1</span>
67 * Explanation:
68 * There is no path that reaches cell (1, 1)​​​​​​​ without exceeding cost k. Thus, the answer is -1.
69 * </div>
70 *  
71 * Constraints:
72 * 
73 * 	1 <= m, n <= 200
74 * 	0 <= k <= 10^3​​​​​​​
75 * 	^​​​​​​​grid[0][0] == 0
76 * 	0 <= grid[i][j] <= 2
77 * 
78 */
79pub struct Solution {}
80
81// problem: https://leetcode.com/problems/maximum-path-score-in-a-grid/
82// discuss: https://leetcode.com/problems/maximum-path-score-in-a-grid/discuss/?currentPage=1&orderBy=most_votes&query=
83
84// submission codes start here
85
86impl Solution {
87    pub fn max_path_score(grid: Vec<Vec<i32>>, k: i32) -> i32 {
88        0
89    }
90}
91
92// submission codes end
93
94#[cfg(test)]
95mod tests {
96    use super::*;
97
98    #[test]
99    fn test_3742() {
100    }
101}
102