Grid Path with Teleportation
In a futuristic logistics network, you control an automated delivery drone navigating a complex grid-based city. Each cell in the city grid contains a specific resource value, which can be positive, negative, or zero. Your mission is to pilot the drone from the top-left corner (0, 0) to the bottom-right corner (R-1, C-1), collecting as much total value as possible. To enhance efficiency, the drone is equipped with a unique, single-use teleportation module. This problem challenges your ability to optimize pathfinding under a special constraint, a common scenario in resource management and route optimization systems.
Implement the function maxGridPathValue that calculates the maximum possible total value the drone can collect while traversing the grid, considering the option to use a single teleport.
Input:
grid: A 2D array of integers (number[][]) representing the city grid. grid[r][c] is the value at cell (r, c). You can only move right (r, c) -> (r, c+1) or down (r, c) -> (r+1, c).teleportCost: A non-negative integer (number) representing the cost incurred if the teleportation module is used. This cost is subtracted from the total collected value.Special Rule for Teleportation:
(r1, c1) to cell (r2, c2), you must satisfy the conditions r2 >= r1 and c2 >= c1. This means you can only teleport to a cell that is 'ahead' or 'to the right' of your current position.grid[r2][c2] to your path sum and subtracts teleportCost. The value of grid[r1][c1] is also included in the path sum (as it's part of the path before teleporting).(r2, c2) to (R-1, C-1) using only right or down moves.Output:
number) representing the maximum total value collected.R (number of rows) and C (number of columns) will be at least 1.grid can be positive, negative, or zero.teleportCost is always non-negative. If teleportCost is very high, it might be optimal not to use the teleport.(0, 0) and end at (R-1, C-1). The values of both start and end cells are included in the path sum.Examples
Example 1
Input:
grid = [[10, 5], [2, 12]], teleportCost = 3
Output:
36
Note:
Grid: [ [10, 5], [2, 12] ], Teleport Cost: 3
Path without teleport: (0,0) -> (0,1) -> (1,1) = 10 + 5 + 12 = 27 (0,0) -> (1,0) -> (1,1) = 10 + 2 + 12 = 24 Max without teleport = 27.
Path with teleport:
Consider a path: (0,0) [value 10] -> (0,1) [value 5]. The sum collected without teleport up to (0,1) is 15.
Now, if we teleport from (0,1) to (1,1): We add grid[1][1] (which is 12) and subtract teleportCost (which is 3).
Total value for this path: 15 + 12 - 3 = 24.
Alternatively, consider teleporting directly from (0,0) to (1,1).
The value collected up to (0,0) is grid[0][0] = 10. Teleport to (1,1) (value 12), cost 3.
Total value: 10 + 12 - 3 = 19.
The optimal path with teleportation is derived from the maximum dp[r][c][0] value (path sum before teleporting) plus the current cell's value minus teleportCost, or by extending an already teleported path. The maximum value for dp[1][1][1] (max value to reach (1,1) having used teleport) is 36. This comes from teleporting to (1,1) from a prior cell that accumulated the maximum possible value without teleport up to that point (which is 27 at (1,1) itself, or earlier cells that contribute to this prefix max). So, 27 (max path sum without teleport up to any cell (pr,pc) with pr<=1, pc<=1) + grid[1][1] (12) - teleportCost (3) = 36.
Comparing 27 (no teleport) and 36 (with teleport), the maximum is 36.
Example 2
Input:
grid = [[1, 100, 1], [1, 1, 1]], teleportCost = 10
Output:
103
Note:
Grid: [ [1, 100, 1], [1, 1, 1] ], Teleport Cost: 10
Path without teleport: (0,0)->(0,1)->(0,2)->(1,2) = 1 + 100 + 1 + 1 = 103. (0,0)->(1,0)->(1,1)->(1,2) = 1 + 1 + 1 + 1 = 4. Max without teleport = 103.
Path with teleport: Consider teleporting from (0,0) to (0,1). Path (0,0) sum is 1. Teleport to (0,1), cost 10. Value at (0,1) is 100. Sum: 1 + 100 - 10 = 91. From (0,1), continue to (0,2) (value 1), then (1,2) (value 1). Total: 91 + 1 + 1 = 93.
Consider teleporting from (0,0) to (1,2). Path (0,0) sum is 1. Teleport to (1,2), cost 10. Value at (1,2) is 1. Sum: 1 + 1 - 10 = -8. This is worse than 103.
It turns out the optimal solution is to not use the teleport, yielding 103.
Example 3
Input:
grid = [[-5, -10], [-20, -1]], teleportCost = 0
Output:
-6
Note:
Grid: [ [-5, -10], [-20, -1] ], Teleport Cost: 0
Path without teleport: (0,0)->(0,1)->(1,1) = -5 + (-10) + (-1) = -16. (0,0)->(1,0)->(1,1) = -5 + (-20) + (-1) = -26. Max without teleport = -16.
Path with teleport: Since teleportCost is 0, we can teleport freely to maximize value. The maximum value to reach any cell (r,c) without teleport, plus grid[r][c] (if it's the teleport destination) is relevant.
One optimal path involves teleporting from (0,0) to (1,1). Value at (0,0) is -5. Teleport to (1,1), value -1, cost 0. Total: -5 + (-1) - 0 = -6. This is better than -16 or -26.
Final result is -6.
Constraints
1 <= R, C <= 500 (where R is the number of rows, C is the number of columns)-1000 <= grid[r][c] <= 10000 <= teleportCost <= 10^9Loading editor...