2456: 秘境寻宝

题目描述

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

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

输入描述

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

输出描述

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