UOJ Logo

NOI.AC

1S 512MB

#1267. 玉米迷宫

Statistics

Description

今年秋天,约翰带着奶牛们去玩玉米迷宫。迷宫可分成$N \times M$个格子,有些格子种了玉 米,种宥玉米的格子无法通行。 迷宫的四条边界上都是种了玉米的格子,其屮只有一个格子 没种,那就是出口。

在这个迷宫里,有一些神奇的传送点6每个传送点由一对点组成,一旦 走入传送点的某个结点, 机器就会强制把你送到传送点的另一头去。所有的传送点都是双向 的,如果你定到了另一头,机器也会把你送回来。

奶牛在一个单位的时间内只能向相邻的四个方向移动一格,不过传送机传送是瞬间完成的。现在$Bessie$在迷宫里迷路了,她只知道目前的位罝在哪里,请你帮助她用最短的时间走出迷宫吧。

Input

第一行:两个用空格分开的整数:$N$和$M$ 第$2 \sim N+1$行:第$i+1$行有$M$个连续的字符,描述了迷宫第$i$行的信息。其中"$\\#$"代 表不能通行的玉米地,"$.$"代表可以通行的草地,"$@$"代表贝西的起始位罝,"$=$"代表迷宫出口,大写字母“$A$”到“$Z$”总是成对出现的,代表一对传送点。

Output

一个整数,表示$Bessie$走出迷宫的最短时间,保证逃离迷宮的路线一定存在。

Sample Input

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

Sample Output

3