Teleporting Maze

Grid Bfs Maze

You are given a 2D grid represented as a list of strings. Each character in the grid can be one of the following:

  • S: The starting position of the maze (exactly one per grid).
  • E: The exit of the maze (exactly one per grid).
  • .: An open path that can be walked on.
  • #: An obstacle that cannot be passed through.
  • T: A teleporter.

Rules of movement:

  1. You can move one step at a time, up, down, left, or right (no diagonal movement).
  2. If you step onto a teleporter cell (T), you have the option, as part of that move, to instantly teleport to any other cell marked with T anywhere in the grid (this teleportation counts as a single move).

Your task is to implement a function that takes the grid as input and returns the minimum number of steps required to reach the exit (E) from the starting position (S). If it is impossible to reach the exit, return -1.

Example:

Suppose the grid is represented as follows:

S.T
.#.
T.E

Here, one possible path is:

  • Start at S (position (0,0)).
  • Move right to . (position (0,1)).
  • Move right to T (position (0,2)).
  • Teleport from this T to the other T at (2,0) in the same move.
  • Move right to . (position (2,1)).
  • Move right to E (position (2,2)).

Thus, the minimum number of steps might be 5 steps. (Note that there might be alternative paths.)

Write a solution that can be run as a standalone program or function. Ensure your code handles various grid sizes and configurations efficiently.