Gem Collector with Supercharge
You are a lead game designer for "Gemstone Odyssey," a popular mobile game. Players navigate a grid-based map, collecting valuable gems. To introduce a new layer of strategy and excitement, you've decided to implement a "Supercharge" ability. This ability allows players to temporarily double the value of gems collected from a specific cell, but it can only be used a limited number of times per level. Your task is to design an algorithm that determines the maximum total gem value a player can collect when traversing a given level grid.
Given a 2D grid representing a level map, where each cell (r, c) contains a certain number of gems, and an integer k representing the total number of Supercharge abilities available, find the maximum total gem value a player can collect.
Players start at the top-left cell (0, 0) and must reach the bottom-right cell (M-1, N-1). From any cell (r, c), a player can only move one step right to (r, c+1) or one step down to (r+1, c).
When a player lands on a cell (r, c), they collect the gems from that cell. If they choose to use a Supercharge ability on that cell, the collected gem value from grid[r][c] is doubled. Each Supercharge ability can be used only once.
The function maxGems will take the following parameters:
grid: A number[][] representing the level map. grid[r][c] is the number of gems in cell (r, c).k: A number representing the total number of Supercharge abilities available.The function should return a number representing the maximum total gem value that can be collected.
grid will be non-negative integers.(0,0) and the ending cell (M-1, N-1), as long as you have k > 0 abilities remaining.Examples
Example 1
Input:
grid = [[10, 5], [2, 8]], k = 1
Output:
33
Note:
Consider all paths and supercharge options: Path 1: (0,0) -> (0,1) -> (1,1). Cells visited: 10, 5, 8.
Example 2
Input:
grid = [[1, 1, 1], [1, 100, 1], [1, 1, 1]], k = 0
Output:
104
Note:
Since k=0, no supercharges can be used. We need to find the path that maximizes the sum of original gem values. The path (0,0) -> (1,0) -> (1,1) -> (2,1) -> (2,2) visits cells with values 1, 1, 100, 1, 1, totaling 104.
Example 3
Input:
grid = [[1, 1, 1], [1, 1, 1], [1, 1, 1]], k = 2
Output:
7
Note:
An optimal path will always visit 5 cells (e.g., (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)). With all gem values being 1, and 2 supercharges available, we can double two of these values. This yields 3 * 1 (normal) + 2 * (2*1) (supercharged) = 3 + 4 = 7.
Constraints
1 <= grid.length <= 500 (M rows)1 <= grid[0].length <= 500 (N columns)0 <= grid[r][c] <= 10000 <= k <= 10grid being null or empty, k being negative). Assume valid inputs per constraints.Loading editor...