Corn Maze

Farmer John took his cows to visit a corn maze this past fall. But this was no ordinary corn maze: it contained several gravity-powered teleporter slides that instantly move a cow from one point in the maze to another.

Each slide works in both directions: a cow can slide instantly from a slide's start to its end, or from its end back to its start. If a cow steps onto a cell holding either end of a slide, she must use the slide.

The outside of the maze is entirely corn, except for a single exit.

The maze is an $N \times M$ grid ($2 \le N \le 300$, $2 \le M \le 300$). Each cell holds exactly one of the following:

• Corn — impassable.
• Grass — easy to walk through.
• A slide endpoint — teleports a cow to the other endpoint of the same slide.
• The exit.

A cow can move from one cell to an adjacent cell (up, down, left, or right) only if neither cell is corn. Moving to an adjacent cell takes $1$ unit of time; sliding from one endpoint of a slide to its other endpoint takes $0$ units of time.

The cells are encoded as follows:

• Corn: #
• Grass: .
• Slide endpoints: a pair of identical uppercase letters (A–Z). Each letter is used by at most one slide, so the two endpoints of a slide share the same letter and no other cell uses that letter.
• Exit: =
• Bessie's current cell: @ (this cell is grass).

Bessie is lost. Given her starting cell @, find the minimum time she needs to reach the exit.

• Line $1$: two space-separated integers $N$ and $M$.
• Lines $2 \ldots N+1$: line $i+1$ contains $M$ characters (no spaces) describing row $i$ of the maze.

• Line $1$: a single integer — the minimum time Bessie needs to reach the exit.