P1825 [USACO11OPEN] Corn Maze S

题目描述

一个 $N×M$ 地图，求从起点到终点的最短时间。

#： 表示是不可以通过的。
.： 表示可以简单的通过。
=： 表示出口。
@：表示起点。
A ~ Z：表示传送装置，同样字母的格子可以互相瞬间传送（遇到必须使用），可以双向传送。在传送过后不会立刻进行第二次传送，即不会卡在传送装置的起点和终点之间来回传送。

移动到四个相邻的格子花费 1 个单位时间。从装置的一个结点到另一个结点不花时间。

输入格式

第一行两个整数 $N \ M( 2 \le N , M \le 300)$。

第 $2 \sim N+1$ 行：第 $i+1$ 行描述地图的第 $i$ 行的情况（共有$M$个字符，每个字符中间没有空格）。

输出格式

一个整数，表示起点到出口所需的最短时间。

输入输出样例 #1

输入 #1

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

输出 #1

3

说明/提示

例如以下矩阵，$N=5,M=6$。

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

唯一的一个装置的结点用大写字母 $\tt{W}$ 表示。

最优方案为：先向右走到装置的结点，花费一个单位时间，再到装置的另一个结点上，花费 $0$ 个单位时间，然后再向右走一个，再向上走一个，到达出口处，总共花费了 $3$ 个单位时间。