← 返回题目列表

AtCoder · icpc2013summer_warmingUp_e

E. 魔法门

中文机器翻译题面 查看原题

说明

Wizard KM 经常忘记关门。
于是他发明了魔法门,用魔法咒语打开,过一段时间后自动关闭。
他家里很多地方都装了门,所以走动变得非常困难。
他想知道在他家的两个地方之间移动的最短时间,所以他施展了魔法,召唤了你,优秀的程序员。
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 (1 \leq H, W \leq 30).
后续 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