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
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 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-04-24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录