EOJ-1839 恶魔之城

http://acm.cs.ecnu.edu.cn/problem.php?problemid=1839

简单最短路径逃离迷宫问题,但要求依次输出路径坐标(任意)

方法是用一个结构体二维数组记下每次满足条件坐标的前一个点,因为BFS的原因,每个点最多只可能访问一次,所以可以用这种方法,最后从终点开始用递归完成输出。

注意在走不通迷宫的时候不要输出路径

 1 #include<map>
 2 #include<set>
 3 #include<list>
 4 #include<cmath>
 5 #include<ctime>
 6 #include<queue>
 7 #include<stack>
 8 #include<cctype>
 9 #include<cstdio>
10 #include<string>
11 #include<cstdlib>
12 #include<cstring>
13 #include<iostream>
14 #include<algorithm>
15 using namespace std;
16 struct node{
17     int x,y;
18 };
19 struct Source{
20     int x,y;
21 }a[205][205];        //记录源点用
22 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};    //方向数组
23 int step[205][205];        //记录步数
24 char mat[205][205];
25 int n,m,ans;
26 int xs,ys;
27 bool fit(int x,int y){
28     return x>=0 && x<n && y>=0 && y<m;        //在图的内部
29 }
30 void bfs(){
31     queue<node> Q;
32     node p,q;
33     int curStep=0;
34     p.x=xs;
35     p.y=ys;
36     Q.push(p);
37     while(!Q.empty()){
38         q=Q.front();
39         Q.pop();
40         curStep=step[q.x][q.y];
41         for(int i=0;i<4;i++){
42             p.x=q.x+dir[i][0];
43             p.y=q.y+dir[i][1];
44             if(fit(p.x,p.y) && (mat[p.x][p.y]=='.' || mat[p.x][p.y]=='E') ){
45                 if(step[p.x][p.y]==0){    
46                     a[p.x][p.y].x=q.x;                    //此处记录满足条件点的前一个点
47                     a[p.x][p.y].y=q.y;
48                     step[p.x][p.y]=curStep+1;
49                     if(mat[p.x][p.y]=='E'){
50                         ans=step[p.x][p.y];
51                         return ;
52                     }
53                     Q.push(p);
54                 }
55             }
56         }
57     }
58     return ;
59 }
60 void dfs(int x,int y){
61     if(x!=xs || y!=ys)dfs(a[x][y].x,a[x][y].y);        //用栈可以保证当起点入栈时可以顺次输出
62     printf("%d %d
",x,y);
63 }
64 int main(){
65     while(~scanf("%d%d",&n,&m)){
66         for(int i=0;i<n;i++)
67             scanf("%s",mat[i]);
68         int xe,ye;
69         for(int i=0;i<n;i++)
70             for(int j=0;j<m;j++){
71                 if(mat[i][j]=='S'){    //记录起点
72                     xs=i;
73                     ys=j;
74                 }
75                 if(mat[i][j]=='E'){    //记录终点
76                     xe=i;
77                     ye=j;
78                 }
79             }
80         memset(step,0,sizeof(step));
81         ans=0;
82         bfs();                            
83         if(ans){
84             printf("%d
",ans);
85             dfs(xe,ye);                    //打印路径
86         }
87         else printf("-1
");
88     }
89     return 0;
90 }
View Code
原文地址:https://www.cnblogs.com/KimKyeYu/p/3143297.html