All problems

Teleporter Maze

Medium · graph traversal

You are given a maze as a rectangular grid of characters:

• "S" is where you start and "E" is the exit. Each appears exactly once.
• "." is an open floor cell and "#" is a wall you cannot enter.
• A lowercase letter is a teleporter. Every letter that appears in the grid appears exactly twice, and those two cells are a pair.

One step moves you to a neighbouring cell above, below, left or right, as long as it is inside the grid and not a wall. Letter cells and the "E" cell can be walked on like floor. Stepping onto a teleporter does not move you anywhere by itself. But when you are standing on a teleporter, you can also spend one step to jump to the other cell with the same letter.

Return the smallest number of steps needed to get from "S" to "E", or -1 if the exit cannot be reached.

Examples

Example 1

Input: grid = [["S", ".", "E"]]

Output: 2

Walk right twice.

Example 2

Input: grid = [["S", ".", ".", ".", "a", "#", "E"], ["#", "#", "#", "#", "#", "#", "a"]]

Output: 6

Walk four steps right to the first a, spend one step to jump to the other a in the second row, then take one step up to E. Without the teleporter there is no way to the exit.

Example 3

Input: grid = [["S", "#", "E"]]

Output: -1

The wall blocks the only way to the exit.

Constraints

• 1 <= rows, cols <= 100
• Every cell is "S", "E", ".", "#" or a lowercase letter.
• There is exactly one "S" and exactly one "E".
• Each lowercase letter that appears in the grid appears exactly twice.
• All rows have the same length.