No submission language available for this problem.

题目描述

假设你是一名勇士，你被派往一座神秘的迷宫中，以找到一件传说中的宝物。迷宫由 $M\times N$ 个方格组成，有的方格内有可以阻碍你前进的陷阱、怪物和魔法，而有的方格内则是安全的。你需要尽快找到传说中的宝物，同时避开有危险的方格，并经过最少的方格。你的任务非常危险，因为你可能会遇到各种各样的陷阱和障碍，例如火焰陷阱、毒液陷阱、巨型怪物、魔法陷阱等等。为了完成任务，你需要从起点开始探索，直到找到传说中的宝物。

输入

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

1)‘@’：你所在的位置；

2)‘.’：可以安全通行的方格；

3)‘#’：有陷阱的方格；

4)‘*’：宝物所在位置。

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

输出

对于每组测试数据，分别输出一行，该行包含你找到宝物需要穿过的最少的方格数目(计数包括初始位置的方块)。如果不可能找到宝物, 则输出 -1。

样例

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

10
8
-1

来源

一本通在线评测 原：仙岛求药