Service Route with Dynamic Toolkit Load
Urban Company technicians often navigate complex city routes to provide services. To ensure efficient and reliable service delivery, it's crucial to minimize disruptions while effectively managing on-hand equipment. This problem models a technician traversing a city grid, optimizing their path to a client location while adhering to strict toolkit weight constraints, which dynamically change based on pickups and drop-offs along the route.
You are given a city grid, where each cell represents a block with an associated disruption cost and a potential weight change to the technician's toolkit (due to picking up or dropping off parts). Your task is to find the minimum total disruption cost to travel from the top-left corner (0, 0) to the bottom-right corner (M-1, N-1).
(0, 0) with a specified initialWeight.(r, c), they incur grid[r][c][0] disruption cost, and their toolkit weight changes by grid[r][c][1].maxCapacity at any point during the journey, nor can it drop below 0.Function Signature:
function findMinDisruption(grid: number[][][], initialWeight: number, maxCapacity: number): number
Parameters:
grid: A 2D array of dimensions M x N, where M is the number of rows and N is the number of columns. Each element grid[r][c] is a tuple [disruptionCost, weightChange].
disruptionCost: A non-negative integer representing the cost incurred when entering cell (r, c).weightChange: An integer representing the change in toolkit weight when traversing cell (r, c). Positive for pickup, negative for drop-off, zero for no change.initialWeight: A non-negative integer representing the toolkit's weight when starting at (0, 0). This weight is before applying grid[0][0][1]'s weightChange.maxCapacity: A positive integer representing the maximum allowed weight for the toolkit.Return Value:
number representing the minimum total disruption cost to reach (M-1, N-1) while satisfying all constraints. Return -1 if no such path exists.(0,0) is always incurred. The weightChange of (0,0) is also applied to initialWeight after entering the cell. The resulting weight must be valid.(M-1, N-1). The disruption cost and weight change of the final cell are included in the total.0 <= currentWeight <= maxCapacity) apply after the weightChange of the current cell has been applied. If applying weightChange violates the constraint, that path becomes invalid from that point.Examples
Example 1
Input:
grid = [[[10, 0], [20, 0]], [[30, 0], [40, 0]]], initialWeight = 5, maxCapacity = 10
Output:
70
Note:
The technician starts at (0,0) with weight 5. Path 1: (0,0) -> (0,1) -> (1,1)
Example 2
Input:
grid = [[[10, 2], [5, -3]], [[15, 0], [20, 1]]], initialWeight = 5, maxCapacity = 7
Output:
35
Note:
The technician starts at (0,0) with weight 5. Path 1: (0,0) -> (0,1) -> (1,1)
Example 3
Input:
grid = [[[1, 10]], [[1, 10]]], initialWeight = 0, maxCapacity = 5
Output:
-1
Note:
The technician starts at (0,0) with weight 0. At (0,0): Current weight 0. New weight: 0 + 10 = 10. This is invalid as 10 > maxCapacity (5). Since the initial step violates the capacity constraint, no valid path can be formed.
Constraints
1 <= M, N <= 50 (grid dimensions)0 <= disruptionCost <= 1000 for any cell (r, c)-500 <= weightChange <= 500 for any cell (r, c)0 <= initialWeight <= maxCapacity1 <= maxCapacity <= 1000disruptionCost values are integers.weightChange values are integers.initialWeight, maxCapacity values are integers.Loading editor...