Strategic Energy Collection
In the popular strategy game "Aetherium Ascent," players navigate a mystical grid to collect "Aether Energy." Your team is developing a new challenge mode where players must strategically utilize a limited number of "Energy Boost" items to maximize their total collected energy. This problem focuses on the core algorithmic challenge of finding the optimal path to achieve the highest possible energy score.
Implement a function getMaxEnergy that calculates the maximum total energy a player can collect when moving through a grid from the top-left corner (0, 0) to the bottom-right corner (M-1, N-1).
The rules are as follows:
(0, 0) and must reach (M-1, N-1).(r, c), you can only move right to (r, c+1) or down to (r+1, c).(r, c) contains grid[r][c] energy points.k "Energy Boost" items. When you pick up energy from a cell, you can choose to use an "Energy Boost" item on that specific cell. If you do, the energy collected from that cell is doubled (grid[r][c] * 2).k items throughout your path.Function Signature:
function getMaxEnergy(grid: number[][], k: number): number
grid: A 2D array of integers M x N, where grid[r][c] represents the energy points available at cell (r, c). All grid[r][c] values are non-negative.k: An integer representing the maximum number of "Energy Boost" items you can use.Return Value:
M >= 1, N >= 1).grid[r][c] are non-negative.(M-1, N-1) from (0,0) following the allowed moves.k can be 0, meaning no boost items are available. k will not be negative.k items can be used on any cell of your path, including the start (0,0) and end (M-1, N-1) cells.Examples
Example 1
Input:
grid = [[10, 5], [2, 8]], k = 0
Output:
23
Note:
With k=0, no boosts can be used. The path (0,0)->(0,1)->(1,1) yields 10+5+8=23. The path (0,0)->(1,0)->(1,1) yields 10+2+8=20. Maximum is 23.
Example 2
Input:
grid = [[1, 10], [100, 1]], k = 1
Output:
202
Note:
With k=1, we can use one boost. The path (0,0)->(1,0)->(1,1) visits cells with values (1, 100, 1). Boosting the value 100 at (1,0) yields 1 + (100*2) + 1 = 202. This is the maximum possible.
Example 3
Input:
grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], k = 2
Output:
46
Note:
Consider the path (0,0)->(1,0)->(2,0)->(2,1)->(2,2) which visits cells with values [1, 4, 7, 8, 9]. To maximize the score with 2 boosts, we would double the two largest values on this path, which are 8 and 9. This yields 1 + 4 + 7 + (82) + (92) = 1 + 4 + 7 + 16 + 18 = 46. Other paths and boost combinations would yield less.
Constraints
1 <= M, N <= 50 (where M is number of rows, N is number of columns)0 <= grid[r][c] <= 10000 <= k <= 10grid inputs (e.g., non-rectangular arrays, non-integer values).O(M*N*K) if the candidate finds a correct solution within that complexity.k is 0 or very large.Loading editor...