李逍遥求药

题目描述

少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。
叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。
迷阵由 M×N 个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。
现在李逍遥想尽快找到仙药，并经过最少的时间。 现在要求你来帮助他实现这个目标。

注意：李逍遥现在学会了新的技能，可以打败一些较弱的怪物，但是需要额外的时间。

下图显示了一个迷阵的样例及李逍遥找到仙药的路线。

输入格式

输入有多组测试数据。
每组测试数据以两个非零整数 M 和 N 开始，两者均不大于 20。
M 表示迷阵行数，N 表示迷阵列数。
接下来有 M 行，每行包含 N 个字符，不同字符分别代表不同含义：

• @：少年李逍遥所在的位置；
• .：可以安全通行的方格；
• #：有怪物的方格（不可通过）；
• a：较弱的怪物，李逍遥可以打败它，但需要额外花费 1 分钟时间；
• *：仙药所在位置。

当在一行中读入的是两个零时，表示输入结束。

输出格式

对于每组测试数据，分别输出一行，该行包含李逍遥找到仙药需要花费的最少时间（单位：分钟）。
每移动一格需要 1 分钟时间，如果打败较弱的怪物（a）需要额外花费 1 分钟时间。
如果他不可能找到仙药，则输出 -1。

样例

输入

8 8
.@a#...#
#....#.#
#.#a##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###
6 5
.*a.#
.#a..
..##.
.....
.#...
....@
9 6
.#..#.
.#.*.#
.####.
..#...
..a...
..#...
..#...
#.@.##
.#..#.
0 0

输出

11
9
-1