noi 2727:仙岛求药

2727:仙岛求药

总时间限制:

1000ms

内存限制:

65536kB

描述

少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。
下图 显示了一个迷阵的样例及李逍遥找到仙药的路线.

输入

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

输出

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

样例输入

8 8

.@##...#

#....#.#

#.#.##..

..#.###.

#.#...#.

..###.#.

...#.*..

.#...###

6 5

.*.#.

.#...

..##.

.....

.#...

....@

9 6

.#..#.

.#.*.#

.####.

..#...

..#...

..#...

..#...

#.@.##

.#..#.

0 0

样例输出

10

8

-1

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 struct abd

 {

     int x;

     int y,step;

 } cur,nxt;

 queue<abd>que;

 int mp[][];

 bool v[][];

 int moe[] = {,,-,,};

 int n,m,li[];

 int tox,toy;

 void bfs(int xx,int xy)

 {

     while(!que.empty())que.pop();

     memset(v,,sizeof(v));

     cur.x=xx;

     cur.y=xy;

     cur.step=;

     que.push(cur);

     v[xx][xy]=;

     while(!que.empty())

     {

         cur=que.front();

         que.pop();

         for(int i=; i<; i++)

         {

             int xxx=cur.x+moe[i];

             int yyy=cur.y+moe[i+];

             if(xxx==tox&&yyy==toy)

             {

                 cout<<cur.step+<<endl;

                 return;

             }

             else if(xxx<=n&&xxx>=&&yyy>=&&yyy<=m&&!mp[xxx][yyy]&&!v[xxx][yyy])

             {

                 nxt.x=xxx;

                 nxt.y=yyy;

                 nxt.step=cur.step+;

                 v[xxx][yyy]=;

                 que.push(nxt);

             }

         }

     }

     cout<<-<<endl;

 }

 int main() {

     string a;

     while(cin>>n>>m)

     {

         if(n==&&m==)break;

         for(int i=; i<=n; i++)

         {

             cin>>a;

             for(int j=; j<a.size(); j++)

             {

                 switch(a[j])

                 {

                     case '.' :mp[i][j+]=;

                         break;

                     case '#' :mp[i][j+]=;    break;

                     case '*' :mp[i][j+]=;tox=i;toy=j+;break;

                     case '@' :mp[i][j+]=;li[]=i;li[]=j+;break;

                 }

             }

         }

         bfs(li[],li[]);

     }

     return ;

 }