211. Minimum Path Cost in a Grid
Medium•
The rectangular grid contains every integer from 0 to m*n - 1 exactly once. Start at any cell in its first row. From a cell you may move to any column of the next row, and must finish in the last row.
The route cost includes every visited cell value plus every move cost. A move from a cell with value v to column nextCol costs moveCost[v][nextCol]. There is no move cost after the final row. Return the minimum total cost without changing either input.
Example 1:
![Grid rows [5,3], [4,0], [2,1], with arrows to both columns of the next row. Move costs are 5 to 4: 14, 5 to 0: 3, 3 to 4: 18, 3 to 0: 6, 4 to 2: 2, 4 to 1: 4, 0 to 2: 9, and 0 to 1: 8. The green route 5 to 0 to 1 has total cost 17, including cell values.](/problems/minimum-path-cost-in-a-grid/example-1.svg)
Input: grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
Output: 17
Explanation: Each arrow is labeled with its move cost; the numbers inside the cells are cell values. The highlighted route is 5 -> 0 -> 1. Its total cost is (5 + 0 + 1) + moveCost[5][1] + moveCost[0][1] = 6 + 3 + 8 = 17. No other route costs less.
Example 2:
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]]
Output: 6
Explanation: Take 2 -> 3. Cell values sum to 5 and moveCost[2][2] is 1.
Example 3:
Input: grid = [[0,1],[2,3]], moveCost = [[1,1],[1,1],[1,1],[1,1]]
Output: 3
Explanation: Take 0 -> 2 with a movement cost of 1.
Constraints
- 2 <= m == grid.length, n == grid[0].length <= 50
- grid is a permutation of 0 through m*n - 1.
- moveCost has m*n rows and n columns.
- 1 <= moveCost[v][col] <= 100
Accepted3/6|Acceptance Rate50.0%