NOI 2727&＃xff1a; 仙岛求药
- 总时间限制:
- 1000ms 内存限制:
- 65536kB
- 描述
- 少年李逍遥的婶婶病了&＃xff0c;王小虎介绍他去一趟仙灵岛&＃xff0c;向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛&＃xff0c;克服了千险万难来到岛的中心&＃xff0c;发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成&＃xff0c;有的方格内有可以瞬秒李逍遥的怪物&＃xff0c;而有的方格内则是安全。现在李逍遥想尽快找到仙药&＃xff0c;显然他应避开有怪物的方格&＃xff0c;并经过最少的方格&＃xff0c;而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。
下图 显示了一个迷阵的样例及李逍遥找到仙药的路线.
输入 - 输入有多组测试数据. 每组测试数据以两个非零整数 M 和 N 开始&＃xff0c;两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义:
1) ‘&＃64;’&＃xff1a;少年李逍遥所在的位置&＃xff1b;
2) ‘.’&＃xff1a;可以安全通行的方格&＃xff1b;
3) ‘#’&＃xff1a;有怪物的方格&＃xff1b;
4) ‘*’&＃xff1a;仙药所在位置。
当在一行中读入的是两个零时&＃xff0c;表示输入结束。 输出 - 对于每组测试数据&＃xff0c;分别输出一行&＃xff0c;该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。 样例输入
-
8 8
.&＃64;##...#
#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###
6 5
.*.#.
.#...
..##.
.....
.#...
....&＃64;
9 6
.#..#.
.#.*.#
.####.
..#...
..#...
..#...
..#...
#.&＃64;.##
.#..#.
0 0
样例输出 -
10
8
-1
思路&＃xff1a;
Bfs多数据输入&＃xff0c;要及时清楚标记
代码&＃xff1a;
1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6
7 int a[21][21],n,m,ex,ey,sx,sy,tep;
8 bool visit[21][21];
9 char mg;
10 int dx[4]&＃61;{1,-1,0,0};//四个方向
11 int dy[4]&＃61;{0,0,1,-1};
12 struct node{
13 int x;int y;int temp;
14 }cur,nxt;
15 queue
16
17 void bfs(){
18 if(ex&＃61;&＃61;sx&&ey&＃61;&＃61;sy){//判断起点是否等于终点&＃xff0c;如果等于&＃xff0c;直接输出0
19 printf("0/n");
20 return ;
21 }while(!q.empty()) q.pop(); //清空队列
22 cur.x&＃61;ex,cur.y&＃61;ey,cur.temp&＃61;0;//将坐标传给结构体
23 visit[ex][ey]&＃61;1;//标记为已访问
24 q.push(cur);//让其入队
25 while(!q.empty()){
26 cur&＃61;q.front();q.pop();//取头元素
27 for(int i&＃61;0;i<&＃61;3;i&＃43;&＃43;){
28 int xx&＃61;cur.x&＃43;dx[i],yy&＃61;cur.y&＃43;dy[i];//xx&＃xff0c;yy是新方向的坐标
29 if(xx>0&&xx<&＃61;n&&yy>0&&yy<&＃61;m&&a[xx][yy]&&!visit[xx][yy]){
30 //判断是否出界&＃xff0c;是否有怪物&＃xff0c;是否被访问过
31 if(xx&＃61;&＃61;sx&&yy&＃61;&＃61;sy){//当更新的新方向等于终点时&＃xff0c;输出
32 printf("%d\n",cur.temp&＃43;1);
33 return ;
34 }
35 nxt.x&＃61;xx,nxt.y&＃61;yy,nxt.temp&＃61;cur.temp&＃43;1;
36 //如果不等于终点&＃xff0c;记录该点信息&＃xff0c;步数&＃43;1&＃xff0c;让其入队
37 visit[nxt.x][nxt.y]&＃61;1;
38 q.push(nxt);
39 }
40 }
41 }
42 printf("-1\n");//如果不能找到仙药&＃xff0c;就输出-1
43 }
44
45 int main(){
46 cin>>n>>m;
47 while(n!&＃61;0&&m!&＃61;0){
48 memset(a,0,sizeof(a));//多组数据输入要清空
49 memset(visit,false,sizeof(visit));
50 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
51 for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){
52 cin>>mg;
53 if(mg&＃61;&＃61;&＃39;#&＃39;) continue;//如果有怪物标记为0
54 a[i][j]&＃61;1;//没有怪物标记为1
55 if(mg&＃61;&＃61;&＃39;&＃64;&＃39;){ ex&＃61;i,ey&＃61;j;};//标记起点坐标
56 if(mg&＃61;&＃61;&＃39;*&＃39;){ sx&＃61;i,sy&＃61;j;};//标记终点坐标
57 }
58 bfs();//输入一遍进行一次广搜
59 cin>>n>>m;
60 }
61 return 0;
62 }
京公网安备 11010802041100号