Maze Teleporters

Graph Bfs Maze

You are given a 2D grid representing a maze where:

  • 'S' marks the start position.
  • 'E' marks the end position.
  • '#' represents walls which cannot be traversed.
  • '.' represents open cells which can be traversed freely.
  • Uppercase letters 'A' to 'Z' represent teleporter cells. All cells marked with the same letter are linked together such that stepping onto one teleporter can instantly transport you to any other cell with the same letter without extra step cost (beyond the cost of moving onto the cell).

You can move up, down, left, or right. Each move to an adjacent cell counts as 1 step. Teleporting does not incur any extra step cost beyond entering the teleporter cell.

Write a function that computes the minimum number of steps required to reach the end position 'E' from the start 'S'. If there is no possible path, your function should return -1.

The input is provided as a list of strings, where each string represents a row of the maze.

Example:

grid = [
  "S.A",
  ".#.",
  "A.E"
]

In the above grid, the teleporter 'A' connects the cell at (0,2) with the cell at (2,0). Your function should determine the minimum number of steps required to travel from 'S' to 'E' using the available moves and teleporters.

Constraints:

  • The grid dimensions can be up to 100 rows and 100 columns.
  • There may be multiple teleporter pairs. Each teleporter letter will appear at least once and possibly more than twice.
  • It is guaranteed that there will be exactly one 'S' and one 'E' in the grid.

Implement your solution in the programming language of your choice.