Minimum Cost to Navigate Factory Floor
In a modern manufacturing facility, autonomous robots navigate complex factory floors to transport materials. Optimizing their movement is crucial for efficiency and cost reduction. This problem simulates a robot's task to find the minimum cost path from a starting point to a destination on a grid-based factory floor, utilizing special teleportation stations when available.
Your task is to implement a function that calculates the minimum cost for a robot to travel from a designated 'Start' cell ('S') to an 'End' cell ('E') on a given factory floor grid. The movement rules and costs are as follows:
1 unit.0 units. This means all cells of a specific teleport type are effectively connected with 0-cost edges.Find the minimum total cost to reach the 'End' cell. If the 'End' cell is unreachable, return -1.
Function Signature:
function minCostNavigation(grid: string[][]): number
grid: A 2D array of characters (string[][]) representing the factory floor. Each character denotes a cell type:
'S': The starting position of the robot.'E': The target destination.'#': An obstacle that cannot be entered.'.': An empty, traversable cell.'A' through 'Z': A teleportation station of a specific type. All stations of the same letter are connected via 0-cost teleportation.Returns: An integer representing the minimum cost to reach 'E' from 'S'. Returns -1 if 'E' is unreachable.
Examples
Example 1
Input:
grid = [["S", ".", "A"], [".", "#", "."], ["A", ".", "E"]]
Output:
4
Note:
Path: S(0,0) -> (0,1) -> A(0,2) (cost 2). From A(0,2), teleport to A(2,0) (cost 0). From A(2,0) -> (2,1) -> E(2,2) (cost 2). Total cost = 2 + 0 + 2 = 4.
Example 2
Input:
grid = [["S", ".", "."], ["#", ".", "."], [".", ".", "E"]]
Output:
5
Note:
Path: S(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> E(2,2). No teleports available. Total cost = 5.
Example 3
Input:
grid = [["S", "#", "."], [".", "#", "."], [".", "#", "E"]]
Output:
-1
Note:
The start 'S' is completely blocked from the end 'E' by obstacles. The end is unreachable.
Example 4
Input:
grid = [["S", ".", "A", ".", "B"], [".", "#", ".", "#", "."], ["A", ".", "C", ".", "E"]]
Output:
6
Note:
Path: S(0,0) -> (0,1) -> A(0,2) (cost 2). From A(0,2), teleport to A(2,0) (cost 0). From A(2,0) -> (2,1) -> (2,2) -> (2,3) -> E(2,4) (cost 4). Total cost = 2 + 0 + 4 = 6. Note that B and C portals are not used in the optimal path.
Constraints
1 <= grid.length, grid[0].length <= 100 (The grid dimensions will not exceed 100x100).grid[r][c] will only contain characters from {'S', 'E', '#', '.', 'A', ..., 'Z'}.Loading editor...