Maximum Path Score in a Grid
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.
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.
Each cell contributes a specific score and incurs an associated cost, according to its cell value:
0: adds0to your score and costs0.1: adds1to your score and costs1.2: adds2to your score and costs1.
Return the maximum score achievable without exceeding a total cost of k, or -1 if no valid path exists.
Note: If you reach the last cell but the total cost exceeds k, the path is invalid.
Example 1
0 1 2 0
Input
grid = [[0,1],[2,0]], k = 1Output
2The optimal path goes through cells with values 0, 2, and 0, giving total score 2 with total cost 1.
Example 2
0 1 1 2
Input
grid = [[0,1],[1,2]], k = 1Output
-1There is no path that reaches cell
(1, 1) without exceeding cost k, so the answer is -1.Constraints
- 1 <= m, n <= 200
- 0 <= k <= 10^3
- ^grid[0][0] == 0
- 0 <= grid[i][j] <= 2