李逍遥寻找仙药的迷阵之旅

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 queueq;//队列
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 }