脚本宝典收集整理的这篇文章主要介绍了2022.4.15 Uva816，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

给出一个箭头迷宫，在每个路口处，如果你从某个方向进入了该路口，那么路口的地面上在靠近你的方向会画有一组箭头，它们相对于你的方向可以是向左，向前，向右，或者是它们的任意组合。

当你从某一方向进入某个入口时，下一步只能在这个入口对应方向上标记的箭头中选一个方向继续行进。在起点时，可以选择任何方向。

给出起点和终点，求它们之间的最短路径。

每条边的长度为1

 

这大概是我第一次做题时意识到语文的重要性 = =

乍一看就是普通的BFS，开始做才发现无从下手。题解也有很多看不懂的地方。

经过我的努力，写出了一个朴实无华的能过样例的题解。。。

#include<iostream>#include<string>#include<algorIThm>#include<cstring>#include<vector>#include<queue>using namespace std;const int MAXN=10;int d[MAXN][MAXN][4];//用于记录BFS过程中节点的父节点bool could[MAXN][MAXN][4][4];//用于标记在坐标ab并面向c时向d是否可以行走char dirs[]="NESW";char turns[]="FLR"; string named;//用于储存每组数据的地图名字struct node{ int r,c,dir;};node nown,start,fin;//分别代表当前、起点、终点node lj[MAXN][MAXN][4];//记录bfs树的路径int dr[]={-1,0,1,0};int dc[]={0,1,0,-1};//这里是为了将NEWS和FLR的信息转化成移动方向，通过上面的两数组一一对应。inline int dir_id(char c){return strchr(dirs,c)-dirs;}inline int turn_id(char c){return strchr(turns,c)-turns;}bool input(){ string dirs; memset(could,0,sizeof(could));//每组数据初始化 char startdir; cin>>named; if(named=="END") return false; cin>>start.r>>start.c>>startdir>>fin.r>>fin.c; nown.dir=dir_id(startdir); //为了防止起始点重复以至于未开始就结束，先走一步. nown.r=start.r+dr[nown.dir]; nown.c=start.c+dc[nown.dir]; int x,y; while(cin>>x,x)//输入0结束 { cin>>y; while(cin>>dirs,dirs!="*") { for(int i=1;i<dirs.length();i++) { //cout<<x<<" "<<y<<" "<<turn_id(dirs[i])<<"n"; could[x][y][dir_id(dirs[0])][turn_id(dirs[i])]=true; } } } return true;}inline bool pd(int r,int c)//判断越界{ return r>0&&r<;mAXN&&c>0&&c<MAXN;}node walk(const node &n,int turn){ node f; int dir=n.dir;//直行时turn=0，无需操作，其余要根据NESW的顺序进行操作 if(turn==1) dir=(dir+3)%4;//左转，即逆时针（相当于转三下） if(turn==2) dir=(dir+1)%4;//右转。即顺时针 f.r=n.r+dr[dir];f.c=n.c+dc[dir];f.dir=dir; return f;}void PRint(node &n){ vector<node>bfstree; while(1)//将起点之后的点一直到终点加入vector中。 { bfstree.push_back(n); if(!d[n.r][n.c][n.dir]) { break; } n=lj[n.r][n.c][n.dir]; } int cnt=0; for(std::vector<node>::iterator i=bfstree.end()-1; i>bfstree.begin(); i--)//倒序输出。 { if(cnt%10){cout<<" ";}//在队首，输出一个空格 else {cout<<" ";}//否则两个 cout<<"("<<(*i).r<<","<<(*i).c<<")"; if(!(++cnt%10)) cout<<"n"; } if(cnt%10){cout<<" ";} else {cout<<" ";} cout<<"("<<start.r<<","<<start.c<<")";//不要忘记输出起点。 if(bfstree.size()%10) cout<<"n"; return;}void solve(){ cout<<named<<"n"; queue<node>Q; memset(d,-1,sizeof(d)); node n=nown; d[n.r][n.c][n.dir]=0;//从初始点走一步之后到达的点距离设为0 Q.push(n); while(!Q.empty())//BFS { n=Q.front(); Q.pop(); if(n.r==fin.r&&n.c==fin.c) { print(n); return; } for(int i=0;i<3;i++)//判断直走、左转、右转 { //cout<<n.r<<" "<<n.c<<" "<<n.dir<<" "<<i<<endl; if(could[n.r][n.c][n.dir][i]) { node v=walk(n,i); if(pd(v.r,v.c)&&d[v.r][v.c][v.dir]==-1) { d[v.r][v.c][v.dir]=d[n.r][n.c][n.dir]+1; lj[v.r][v.c][v.dir]=n; Q.push(v); } } } } cout<<" No Solution Possible"<<"n"; return;}int main(){ std::ios::sync_with_stdio(false); while(input()) { solve(); }; return 0;}

脚本宝典总结

以上是脚本宝典为你收集整理的2022.4.15 Uva816全部内容，希望文章能够帮你解决2022.4.15 Uva816所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。