十大信誉官网2727:仙岛求药

2727:仙岛求药

总时间范围:
1000ms

内部存款和储蓄器约束:
65536kB

描述
少年李逍遥的二姨病了,王小虎介绍他去后生可畏趟仙灵岛,向仙女二嫂要仙丹救大姨。叛逆但孝顺的李逍遥闯进了仙灵岛,征服了千险万难来到岛的骨干,发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成,有的方格内有能够弹指秒李逍遥的鬼怪,而部分方格内则是安全。未来李逍遥想尽快找到仙药,显明他应避开有怪物的方格,并通过起码的方格,並且这里会有私人民居房人物等待着他。今后供给你来扶助他落实这一个目的。
下图 展现了四个迷阵的样例及李逍遥找到仙药的路径.
十大信誉官网 1

输入
输入有多组测验数据. 每组测验数据以三个非零整数 M 和 N
开始,两个均不超过20。M 表示迷阵行数, N 代表迷阵列数。接下来有 M 行,
每行蕴涵N个字符,分化字符分别代表不相同含义:
1) ‘@’:少年李逍遥所在的职分;
2) ‘.’:能够清心少欲畅通的方格;
3) ‘#’:有怪物的方格;
4) ‘*’:仙药所在地方。
当在朝气蓬勃行中读入的是八个零时,表示输入完成。

输出
对此每组测量试验数据,分别出口生机勃勃行,该行满含李逍遥找到仙药须要通过的起码的方格数目(计数富含初始地方的四方)。要是她不或者找到仙药,
则输出 -1。

样例输入
8 8
.@##…#

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

样例输出
10
8
-1

bfs裸题,注意每组数据之间的衔接

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 int bgx,bgy,edx,edy;
 7 const int MAXN=1001;
 8 int map[MAXN][MAXN];
 9 bool vis[MAXN][MAXN];
10 int xx[6]={-1,+1,0,0};
11 int yy[6]={0,0,-1,+1};
12 int n,m;
13 struct node
14 {
15     int x;
16     int y;
17     int step;
18 }cur,nxt;
19 queue<node>q;
20 void bfs(int x,int y)
21 {
22     while(q.size()!=0)q.pop();
23     cur.x=x;    cur.y=y;    cur.step=0;
24     q.push(cur);
25     vis[x][y]=1;
26     int flag=0;
27     while(q.size()!=0)
28     {
29         node p=q.front();
30         q.pop();
31         for(int i=0;i<4;i++)
32         {
33             int wx=p.x+xx[i];
34             int wy=p.y+yy[i];
35             if(wx>=1&&wx<=n&&wy>=1&&wy<=m&&vis[wx][wy]==0&&map[wx][wy]!=1)
36             {
37                 if(map[wx][wy]==2)
38                 {
39                     printf("%d\n",p.step+1);
40                     flag=1;
41                     break;
42                 }
43                 else
44                 {
45                     nxt.x=wx;
46                     nxt.y=wy;
47                     nxt.step=p.step+1;
48                     q.push(nxt);
49                     vis[wx][wy]=1;
50                 }
51             }
52         }
53         if(flag==1)break;
54     }
55     if(flag==0)
56     printf("-1\n");
57 }
58 int main()
59 {
60     while(scanf("%d%d",&n,&m))
61     {
62         memset(map,0,sizeof(map));
63         memset(vis,0,sizeof(vis));
64         if(n==0&&m==0)break;
65         for(int i=1;i<=n;i++)
66         {
67             for(int j=1;j<=m;j++)
68             {
69                 char c;
70                 cin>>c;
71                 if(c=='@')     {bgx=i;bgy=j;map[i][j]=1;}
72                 if(c=='*')    {edx=i;edy=j;map[i][j]=2;}
73                 if(c=='#')     {map[i][j]=1;}
74                 if(c=='.')     {map[i][j]=0;}
75             }
76         }
77         bfs(bgx,bgy);
78     }
79     return 0;
80 }