You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

This past fall, Farmer John took the cows to visit a corn maze. But this wasn't just any corn maze: it featured several gravity-powered teleporter slides, which cause cows to teleport instantly from one point in the maze to another. The slides work in both directions: a cow can slide from the slide's start to the end instantly, or from the end to the start. If a cow steps on a space that hosts either end of a slide, she must use the slide.

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

The maze can be represented by an N x M (2 <= N <= 300; 2 <= M <= 300) grid. Each grid element contains one of these items:

* Corn (corn grid elements are impassable)

* Grass (easy to pass through!)

* A slide endpoint (which will transport a cow to the other endpoint)

* The exit

A cow can only move from one space to the next if they are adjacent and neither contains corn. Each grassy space has four potential neighbors to which a cow can travel. It takes 1 unit of time to move from a grassy space to an adjacent space; it takes 0 units of time to move from one slide endpoint to the other.

Corn-filled spaces are denoted with an octothorpe (#). Grassy spaces are denoted with a period (.). Pairs of slide endpoints are denoted with the same uppercase letter (A-Z), and no two different slides have endpoints denoted with the same letter. The exit is denoted with the equals sign (=).

Bessie got lost. She knows where she is on the grid, and marked her current grassy space with the 'at' symbol (@). What is the minimum time she needs to move to the exit space?

输入格式

Line 1: Two space separated integers: N and M

Lines 2..N+1: Line i+1 describes row i of the maze: M characters (no spaces)

输出格式

Line 1: An integer, corresponding to the shortest time that Bessie needs to exit the maze.

题目大意

奶牛们去一个 $N\times M$ 玉米迷宫，$2 \leq N \leq 300,2 \leq M \leq300$。

迷宫里有一些传送装置，可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用。

如果一头奶牛处在这个装置的起点或者终点，这头奶牛就必须使用这个装置，奶牛在传送过后不会立刻进行第二次传送，即不会卡在传送装置的起点和终点之间来回传送。

玉米迷宫除了唯一的一个出口都被玉米包围。

迷宫中的每个元素都由以下项目中的一项组成：

1. 玉米，# 表示，这些格子是不可以通过的。
2. 草地，. 表示，可以简单的通过。
3. 传送装置，每一对大写字母 $\tt{A}$ 到 $\tt{Z}$ 表示。
4. 出口，= 表示。
5. 起点， @ 表示

奶牛能在一格草地上可能存在的四个相邻的格子移动，花费 $1$ 个单位时间。从装置的一个结点到另一个结点不花时间。

5 6
###=##
#.W.##
#.####
#.@W##
######

3

提示

Sample Explanation:

###=##
#.W.##
#.####
#.@W##
######

The endpoints of the only slide are marked with capital letters W.

The optimal strategy (which takes 3 units of time) is to: Move right to the slide endpoint using 1 unit of time, transport to the other endpoint using 0 units of time, move right using 1 unit of time, and move up to the exit using 1 unit of time.