BFS求最短路 Abbottt's Revenge UVa 816

时间:2021-09-15 21:32:53

BFS求最短路 Abbottt's Revenge UVa 816

本题的题意是输入起点,朝向和终点,求一条最短路径(多解时任意输出一个即可)

本题的主要代码是bfs求解,就是以下代码中的slove的主要部分,通过起点按照路径的长度来寻找最短路径,输出最先到终点的一系列点

以下代码中,用两个数组保存四个方向,运用函数walk()表示结点的方向变换,通过d[][][]保存路径的长度,p[][][]保存路径中的结点,has_edge[][][][]标记行得通的路径,同时用队列先进先出,层次遍历所有结点,用vector存储将要输出的结点,防止内存空间不够大

 #include<stdio.h>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<iostream>
using namespace std;
const int maxn=;
char name[];
int r0,c0,r1,c1,r2,c2,dir,turn;
char dir0,str[];
int has_edge[maxn][maxn][maxn][maxn]; //表示当前状态,是否可以沿turn的方向行走
int d[maxn][maxn][maxn]; //表示初始状态到(r1,c1,dir)的最短路的长度
string maze_name; const char* dirs="NESW";
const char* turns="FLR";
const int dr[]={-,,,}; //行
const int dc[]={,,,-}; //列
int dir_id(char c){return strchr(dirs,c)-dirs;}
int turn_id(char c){return strchr(turns,c)-turns;} struct Node{
int dir,r,c;
Node(int r=,int c=,int dir=):r(r),c(c),dir(dir){}
}; Node p[maxn][maxn][maxn]; //保存状态 Node walk(const Node& u,int turn){
int dir=u.dir;
if(turn==) dir=(dir+)%; //逆时针
if(turn==) dir=(dir+)%; //顺时针
return Node(u.r+dr[dir],u.c+dc[dir],dir);
} bool inside(int r,int c){
if(r>=&&r<=&&c>=&&c<=) return true;
return false;
} void print_ans(Node u){
vector<Node> nodes;
for(;;){
nodes.push_back(u);
if(d[u.r][u.c][u.dir]==) break;
u=p[u.r][u.c][u.dir];
}
nodes.push_back(Node(r0,c0,dir));
int cnt=;
for(int i=nodes.size()-;i>=;i--){
if(cnt%==) printf(" ");
printf(" (%d,%d)",nodes[i].r,nodes[i].c);
if(++cnt%==) printf("\n");
// printf("(%d,%d)%c",nodes[i].r,nodes[i].c,++cnt%10?' ':'\n');
}
if(nodes.size()%!=) printf("\n");
} void solve(){
memset(d,-,sizeof(d));
queue<Node> q;
d[r1][r2][dir]=;
Node u(r1,c1,dir);
q.push(u);
while(!q.empty()){
u=q.front();
q.pop();
if(u.r==r2&&u.c==c2){
print_ans(u);
return;
}
for(int i=;i<;i++){
Node v=walk(u,i);
if(d[v.r][v.c][i]<&&inside(v.r,v.c)&&has_edge[u.r][u.c][u.dir][i]){
d[v.r][v.c][v.dir]=d[u.r][u.c][u.dir]+;
p[v.r][v.c][v.dir]=u;
q.push(v);
}
}
}
printf("No Solution Possible\n");
} int main(){
freopen("in.txt","r",stdin);
while(scanf("%s",name)){
memset(has_edge,,sizeof(has_edge));
if(strcmp(name,"END")==) break;
scanf("%d%d",&r0,&c0);
scanf("%s",&dir0);
scanf("%d%d",&r2,&c2);
dir=dir_id(dir0);
r1=r0+dr[dir];
c1=c0+dc[dir];
int pr,pc,pdir,pturn;
while(scanf("%d",&pr)&&pr){
scanf("%d",&pc);
while(scanf("%s",str)){
if(str[]=='*'){break;}
pdir=dir_id(str[]);
int len=strlen(str);
for(int i=;i<len;i++){
pturn=turn_id(str[i]);
has_edge[pr][pc][pdir][pturn]=;
}
}
}
cout<<name<<endl;
solve();
}
return ;
}