题目描述

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

数据范围与提示： M，N≤20

输入格式

输入有多组测试数据. 每组测试数据以两个非零整数 M 和 N 开始，两者均不大于 20。M 表示迷阵行数, N 表示迷阵列数。接下来有 M 行, 每行包含 N 个字符,不同字符分别代表不同含义: 1)‘@’：rain所在的位置； 2)‘.’：可以安全通行的方格； 3)‘#’：有猛兽的方格； 4)‘*’：地图所在位置。 当在一行中读入的是两个零时，表示输入结束。

输出格式

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

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

10
8
-1

提示

数据范围与提示： M，N≤20