Frontend School

Minimum Cost to Navigate Factory Floor

DSA
medium

Minimum Cost to Navigate Factory Floor

Medium
Graph
BFS
Shortest Path
0-1 BFS

Overview

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.

What you need to do / Task

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. Adjacent Movement: Moving to an adjacent cell (up, down, left, or right) costs 1 unit.
  2. Teleportation: If the robot is on a teleport station (represented by an uppercase letter 'A' through 'Z'), it can instantly teleport to any other teleport station of the same type (same letter) at a cost of 0 units. This means all cells of a specific teleport type are effectively connected with 0-cost edges.
  3. Obstacles: The robot cannot move into obstacle cells ('#').

Find the minimum total cost to reach the 'End' cell. If the 'End' cell is unreachable, return -1.

Input & output

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.

Clarifications

  • The grid will always contain exactly one 'S' and exactly one 'E'.
  • Movement is restricted to 4 directions: up, down, left, right.
  • Teleportation is only possible between stations of the exact same letter type.
  • The robot can start on 'S' and end on 'E'. 'S' and 'E' cannot be teleport stations or obstacles themselves.

Examples

1

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.

2

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.

3

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.

4

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

Constraints & assumptions

  • 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'}.
  • All cells represented by uppercase letters 'A' through 'Z' are considered teleport stations.
  • The cost will always be non-negative.

Out of scope

  • Reconstructing the actual path taken by the robot.
  • Handling malformed input grids (e.g., multiple 'S' or 'E', invalid characters).

What interviewers evaluate

  • Correct application of shortest path algorithm: Demonstrates understanding and correct implementation of a graph traversal algorithm suitable for varying edge weights (0 and 1).
  • Efficient graph modeling: Effectively translates the grid and teleportation rules into a solvable graph problem, specifically handling 0-cost teleport edges.
  • State management: Correctly manages visited states and accumulated costs to avoid cycles and redundant computations.
  • Edge case handling: Addresses scenarios such as unreachable targets, or grids without any teleport stations.
  • Code quality: Writes clean, readable, and well-structured code.

Loading editor...