说明
于是他发明了魔法门,用魔法咒语打开,过一段时间后自动关闭。
他家里很多地方都装了门,所以走动变得非常困难。
他想知道在他家的两个地方之间移动的最短时间,所以他施展了魔法,召唤了你,优秀的程序员。
KM 的房子由方形单元格矩阵组成。单元格是以下之一。
. empty # wall ^ start $ goal a-h magic circle A-H magic door他可以将一个单元格移动到其 4- 一秒钟就到邻居了。
他可以进入空牢房、开始、目标、魔法阵,并打开魔法门。
房子被围墙包围了,他不能出去。
在魔法阵上,他可以通过消耗任意数量的MP(魔力)来施展魔法。这需要一点时间。当他使用 x MP,期间对应的魔法门打开 x 秒。
他可以进入当时关闭的门。
可能有多个相同的魔法阵或相同的魔法门。这样的话,当他对任意一个魔法阵施展魔法咒语时,所有对应的魔法门都会打开。
一开始,他的MP是 0。可以在任意时间进行冥想并恢复MP。冥想每分钟需要一秒钟 1 MP。 MP 没有上限。
求从起点到目标的最短时间。
输入
后续 H 行 W 字符 \{c_{ij}\} 是KM家的地图。
每个字符 c_{ij} 是字母之一
., #, ^, $, a-h, A-H.地图上只有一个起点和一个目标。
输出
如果无法达到目标,则输出
-1 。
示例输入
1 3 ^.$
示例输出
2
示例输入
1 4 ^aA$
示例输出
5
示例输入
1 4 ^aB$
示例输出
-1
示例输入
3 3 ^AB a#A b#$
示例输出
19