2727:仙岛求药

2018-06-17 22:43:20来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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 }

 


标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P2066 机器分配

下一篇:读书笔记 effective c++ Item 54 让你自己熟悉包括TR1在内的标准