Scenic Route Finder
Uber's mapping and routing systems are crucial for efficient operations. Beyond just the fastest route, sometimes we need to consider alternative factors, like a "scenic value" for premium rides or specialized deliveries. This problem simulates a scenario where we need to identify all possible routes that meet a specific "scenic sum" criterion, mimicking a feature that might enhance rider experience or optimize specialized delivery logistics.
Implement a function findAllScenicPaths that takes a grid representing a city map, a start coordinate, an end coordinate, and a target scenic sum. The function should return all unique paths from the start to the end cell where the sum of scenic values of all cells in the path (including start and end) exactly equals targetScenicSum.
grid: number[][] - A 2D array where grid[r][c] represents the scenic value of the cell at row r and column c.
start: [number, number] - A tuple [r, c] indicating the starting cell coordinates.
end: [number, number] - A tuple [r, c] indicating the ending cell coordinates.
targetScenicSum: number - The exact sum of scenic values that a valid path must achieve.
Returns: string[][] - An array of unique paths. Each path is represented as an array of strings, where each string is a cell coordinate in "row,col" format (e.g., "0,0", "1,0"). The order of paths in the output array does not matter. If no such paths exist, return an empty array.
targetScenicSum.Examples
Example 1
Input:
grid = [[1, 2], [3, 4]], start = [0, 0], end = [1, 1], targetScenicSum = 8
Output:
[["0,0","1,0","1,1"]]
Note:
Path (0,0) -> (1,0) -> (1,1) has scenic values 1 + 3 + 4 = 8, matching the target. Path (0,0) -> (0,1) -> (1,1) has sum 1 + 2 + 4 = 7, which is not 8.
Example 2
Input:
grid = [[1, 2, 1], [3, 4, 5], [6, 7, 8]], start = [0, 0], end = [2, 2], targetScenicSum = 21
Output:
[["0,0","1,0","1,1","1,2","2,2"]]
Note:
Path (0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,2) has scenic values 1 + 3 + 4 + 5 + 8 = 21, matching the target.
Example 3
Input:
grid = [[1, 1], [1, 1]], start = [0, 0], end = [1, 1], targetScenicSum = 10
Output:
[]
Note:
The maximum possible scenic sum for any valid path from (0,0) to (1,1) in this grid is 3 (e.g., 1+1+1). No path can sum to 10.
Constraints
1 <= grid.length, grid[0].length <= 10 (Grid dimensions M x N)0 <= grid[r][c] <= 100 (Scenic value of each cell)0 <= targetScenicSum <= 1000start[0], end[0] are valid row indices.start[1], end[1] are valid column indices.Loading editor...