秘境寻宝

题目描述

在美洲大陆上，曾经生活着许多印第安人，传说他们在祭祀的时候经常会把黄金器具扔到一个湖里，后来许多人都想找到这个黄金湖。奶牛 rain 也想找到它。终于 rain 在热带雨林中发现了一些线索，但是他想要的地图放在一个区域的中心位置，被古印第安人设置了各类障碍。但是要想到达黄金湖必须要找到这个地图。区域被树林隔成 $M \times N$ 个方格，有的方格内居住着猛兽，而有的方格内是安全的。现在 rain 想尽快找到地图，显然他应避开有猛兽的方格，并经过最少的方格，成功拿到地图。

输入格式

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

1. @：rain 所在的位置；
2. .：可以安全通行的方格；
3. #：有猛兽的方格；
4. *：地图所在位置。

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

输出格式

对于每组测试数据，分别输出一行，该行包含 rain 找到地图需要穿过的最少的方格数目（计数包括初始位置的方块）。如果他不可能找到地图，则输出 -1。

样例输入 #1

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

样例输出 #1

10
8
-1

数据范围

$M, N \le 20$

知识点与难度

本题涉及的知识点从属于 GESP六级（BFS 最短路搜索、多组数据处理），难度等级：⭐⭐⭐。

测试点分布