首页 > 代码库 > NOI 2727:仙岛求药 x
NOI 2727:仙岛求药 x
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。
下图 显示了一个迷阵的样例及李逍遥找到仙药的路线.
- 输入
- 输入有多组测试数据. 每组测试数据以两个非零整数 M 和 N 开始，两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义:
1) ‘@’：少年李逍遥所在的位置；
2) ‘.’：可以安全通行的方格；
3) ‘#’：有怪物的方格；
4) ‘*’：仙药所在位置。
当在一行中读入的是两个零时，表示输入结束。 - 输出
- 对于每组测试数据，分别输出一行，该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。
- 样例输入
8 8.@##...##....#.##.#.##....#.###.#.#...#...###.#....#.*...#...###6 5.*.#..#.....##.......#.......@9 6.#..#. .#.*.# .####. ..#... ..#... ..#... ..#... #.@.## .#..#. 0 0
- 样例输出
108-1
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<queue> 6 #define M 21 7 8 using namespace std; 9 10 int m,n,sx,sy,ex,ey;11 int jz[M][M];12 bool v[M][M];13 int dx[4]={0,0,1,-1},14 dy[4]={1,-1,0,0};//几个方向 15 16 struct a{17 int x,y,step;18 }nex,noww;19 20 queue<a>q;21 22 void bfs()23 {24 if(sx==ex&&sy==ey)//防止出现起点等于终点的情况 25 {26 printf("0\n");27 return;28 }29 while(!q.empty()) q.pop();//因为有多组数据需要进行清空30 noww.x=sx; noww.y=sy; noww.step=0;//初始化 31 v[sx][sy]=1;//进行标记已经被访问32 q.push(noww); 33 while(!q.empty())34 {35 noww=q.front();//取出队头元素36 q.pop();37 for(int i=0;i<4;i++)38 {39 int xx=noww.x+dx[i],yy=noww.y+dy[i];40 if(xx>0&&xx<=m&&yy>0&&yy<=n&&!v[xx][yy]&&jz[xx][yy])41 {42 if(xx==ex&&yy==ey)//如果到达终点 43 {44 printf("%d\n",noww.step+1);//输出答案45 return;//不能够写break！因为break只能够跳出for循环 46 }47 nex.x=xx; nex.y=yy; nex.step=noww.step+1;48 v[xx][yy]=1;//标记 49 q.push(nex);//进队 50 }51 } 52 }53 cout<<"-1"<<endl;//没有找到输出-1 54 }55 56 int main()57 {58 char ch;59 while(scanf("%d%d",&m,&n)!=EOF)//在不清楚拥有几组数据的情况下 60 {61 if(m!=0&&n!=0)62 {63 memset(jz,0,sizeof(jz));64 memset(v,0,sizeof(v));65 for(int i=1;i<=m;i++)66 for(int j=1;j<=n;j++)67 {68 cin>>ch;69 if(ch==‘@‘)//李(起)逍(点)遥 70 {71 sx=i;sy=j;72 }73 if(ch==‘*‘)//仙(终)药(点) 74 {75 ex=i;ey=j;76 }77 if(ch==‘#‘)//怪(障)物(碍) 78 {79 continue;80 }81 jz[i][j]=1;82 }83 bfs();84 }85 else break;86 }87 return 0;88 }
NOI 2727:仙岛求药 x
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。