2304. Minimum Path Cost in a Grid Medium

1/**
2 * [2304] Minimum Path Cost in a Grid
3 *
4 * You are given a 0-indexed m x n integer matrix grid consisting of distinct integers from 0 to m * n - 1. You can move in this matrix from a cell to any other cell in the next row. That is, if you are in cell (x, y) such that x < m - 1, you can move to any of the cells (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1). Note that it is not possible to move from cells in the last row.
5 * Each possible move has a cost given by a 0-indexed 2D array moveCost of size (m * n) x n, where moveCost[i][j] is the cost of moving from a cell with value i to a cell in column j of the next row. The cost of moving from cells in the last row of grid can be ignored.
6 * The cost of a path in grid is the sum of all values of cells visited plus the sum of costs of all the moves made. Return the minimum cost of a path that starts from any cell in the first row and ends at any cell in the last row.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2022/04/28/griddrawio-2.png" style="width: 301px; height: 281px;" />
10 * Input: grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
11 * Output: 17
12 * Explanation: The path with the minimum possible cost is the path 5 -> 0 -> 1.
13 * - The sum of the values of cells visited is 5 + 0 + 1 = 6.
14 * - The cost of moving from 5 to 0 is 3.
15 * - The cost of moving from 0 to 1 is 8.
16 * So the total cost of the path is 6 + 3 + 8 = 17.
17 *
18 * Example 2:
19 *
20 * Input: grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]
21 * Output: 6
22 * Explanation: The path with the minimum possible cost is the path 2 -> 3.
23 * - The sum of the values of cells visited is 2 + 3 = 5.
24 * - The cost of moving from 2 to 3 is 1.
25 * So the total cost of this path is 5 + 1 = 6.
26 *
27 *  
28 * Constraints:
29 *
30 * m == grid.length
31 * n == grid[i].length
32 * 2 <= m, n <= 50
33 * grid consists of distinct integers from 0 to m * n - 1.
34 * moveCost.length == m * n
35 * moveCost[i].length == n
36 * 1 <= moveCost[i][j] <= 100
37 *
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/minimum-path-cost-in-a-grid/
42// discuss: https://leetcode.com/problems/minimum-path-cost-in-a-grid/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47    pub fn min_path_cost(grid: Vec<Vec<i32>>, move_cost: Vec<Vec<i32>>) -> i32 {
48        let m = grid.len();
49        let n = grid[0].len();
50
51        let mut dp = vec![vec![i32::MAX; n]; m];
52        for i in 0..grid[0].len() {
53            dp[0][i] = grid[0][i];
54        }
55
56        for i in 1..grid.len() {
57            for j in 0..grid[i].len() {
58                dp[i][j] = grid[i][j]
59                    + dp[i - 1]
60                        .iter()
61                        .enumerate()
62                        .map(|(index, v)| *v + move_cost[grid[i - 1][index] as usize][j])
63                        .min()
64                        .unwrap();
65            }
66        }
67
68        *dp[m - 1].iter().min().unwrap() as i32
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_2304() {
80        assert_eq!(
81            Solution::min_path_cost(
82                vec![vec![5, 3], vec![4, 0], vec![2, 1]],
83                vec![
84                    vec![9, 8],
85                    vec![1, 5],
86                    vec![10, 12],
87                    vec![18, 6],
88                    vec![2, 4],
89                    vec![14, 3]
90                ]
91            ),
92            17
93        );
94
95        assert_eq!(
96            Solution::min_path_cost(
97                vec![vec![5, 1, 2], vec![4, 0, 3]],
98                vec![
99                    vec![12, 10, 15],
100                    vec![20, 23, 8],
101                    vec![21, 7, 1],
102                    vec![8, 1, 13],
103                    vec![9, 10, 25],
104                    vec![5, 3, 2]
105                ]
106            ),
107            6
108        );
109    }
110}
111