NOI 2727 仙岛求药

NOI 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 
 7 int a[21][21],n,m,ex,ey,sx,sy,tep;
 8 bool visit[21][21];
 9 char mg;
10 int dx[4]={1,-1,0,0};//四个方向 
11 int dy[4]={0,0,1,-1};
12 struct node{
13     int x;int y;int temp;
14 }cur,nxt;
15 queue<node>q;//队列 
16 
17 void bfs(){
18     if(ex==sx&&ey==sy){//判断起点是否等于终点，如果等于，直接输出0 
19         printf("0/n");
20         return ;
21     }while(!q.empty()) q.pop(); //清空队列 
22     cur.x=ex,cur.y=ey,cur.temp=0;//将坐标传给结构体 
23     visit[ex][ey]=1;//标记为已访问 
24     q.push(cur);//让其入队 
25     while(!q.empty()){
26         cur=q.front();q.pop();//取头元素 
27         for(int i=0;i<=3;i++){
28             int xx=cur.x+dx[i],yy=cur.y+dy[i];//xx，yy是新方向的坐标 
29             if(xx>0&&xx<=n&&yy>0&&yy<=m&&a[xx][yy]&&!visit[xx][yy]){
30                 //判断是否出界，是否有怪物，是否被访问过 
31                 if(xx==sx&&yy==sy){//当更新的新方向等于终点时，输出 
32                     printf("%d
",cur.temp+1);
33                     return ;
34                 }
35                 nxt.x=xx,nxt.y=yy,nxt.temp=cur.temp+1;
36                 //如果不等于终点，记录该点信息，步数+1，让其入队 
37                 visit[nxt.x][nxt.y]=1;
38                 q.push(nxt);
39             }
40         }
41     }
42     printf("-1
");//如果不能找到仙药，就输出-1 
43 }
44 
45 int main(){
46     cin>>n>>m;
47     while(n!=0&&m!=0){
48         memset(a,0,sizeof(a));//多组数据输入要清空 
49         memset(visit,false,sizeof(visit));
50         for(int i=1;i<=n;i++)
51           for(int j=1;j<=m;j++){
52                 cin>>mg;
53                 if(mg=='#') continue;//如果有怪物标记为0 
54                 a[i][j]=1;//没有怪物标记为1 
55                 if(mg=='@'){ ex=i,ey=j;};//标记起点坐标 
56                 if(mg=='*'){ sx=i,sy=j;};//标记终点坐标 
57           }
58         bfs();//输入一遍进行一次广搜 
59         cin>>n>>m;
60     }
61     return 0;
62 }