uva816 abbots的复仇 bfs+方向朝向

本文主要是介绍uva816 abbots的复仇 bfs+方向朝向，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#include<sstream>
#include<iostream>
#include<vector>
using namespace std;
const int maxn=10;
const char* dir="NESW";///不能是(NEWS)，这样下面的walk里面的求余才能对应到对应的位置
const char* turn="FLR";
const int dr[]={-1,0,1,0};///NESW
const int dc[]={0,1,0,-1};///d数组是起点到某点，某朝向的最短距离。has是某点某朝向是否存在转弯
int d[maxn][maxn][4],has[maxn][maxn][4][3];
string s;
int r0,c0,r1,c1,dir1,r2,c2;
char d1;struct Node{int dir,r,c;Node(){}Node(int dd,int rr,int cc):dir(dd),r(rr),c(cc){}
};
Node p[maxn][maxn][4];///记录节点的父亲节点。int translated(char c){///返回dir数组中对应的+，-关系return strchr(dir,c)-dir;///strchr：在dir找到指向c的指针
}int translatet(char c){///返回turn数组中对应的+，-关系return strchr(turn,c)-turn;
}Node walk(Node u,int turn){///行走函数，判断下一步的位置int di=u.dir;if(turn==2)///计算右转后的方向di=(di+1)%4;if(turn==1)///计算左转后的方向di=(di+3)%4;return Node(di,u.r+dr[di],u.c+dc[di]);///直走即是延当前方向
}void init(){
string pos,str;
stringstream ss;
int r,c,t1,t2;
memset(has,0,sizeof(has));
memset(d,-1,sizeof(d));
if(d1=='N'){r1=r0-1;c1=c0;
}
else if(d1=='E'){r1=r0;c1=c0+1;
}
else if(d1=='S'){r1=r0+1;c1=c0;
}
else if(d1=='W'){r1=r0;c1=c0-1;
}
getchar();
while(getline(cin,pos)&&pos!="0"){///通过getchar getline stringstream获取输入流特定格式的字符或字符串。ss<<pos;ss>>r>>c;while(ss>>str){///每次传入一个字符串，结尾是"\0"if(str[0]!='*'){t1=translated(str[0]);for(int i=1;i<str.length();i++){t2=translatet(str[i]);has[r][c][t1][t2]=1;///初始化has数组}}}ss.clear();///切记清空ss
}
}void print(Node n){///从终点开始回溯到起点。vector<Node> ve;ve.clear();while(1){ve.push_back(n);if(n.r==r1&&n.c==c1&&n.dir==dir1)///if(d[n.r][n.c][n.dir]==0)break;n=p[n.r][n.c][n.dir];}ve.push_back(Node(dir1,r0,c0));///记住起始点是没有在里面的，所以要加上int cnt=0;for(int i=ve.size()-1;i>=0;i--){///vector实现栈的功能，cnt控制格式if(cnt%10==0)printf(" ");printf(" (%d,%d)",ve[i].r,ve[i].c);if(++cnt%10==0)printf("\n");}if(ve.size()%10!=0) printf("\n");
}void solve(){///bfsqueue<Node> q;dir1=translated(d1);Node n=Node(dir1,r1,c1);d[r1][c1][dir1]=0;//has[r0][c0][dir1][0]=1;q.push(n);while(!q.empty()){Node n2=q.front();q.pop();if(n2.r==r2&&n2.c==c2){print(n2);return;}for(int i=0;i<3;i++){Node v=walk(n2,i);if(has[n2.r][n2.c][n2.dir][i]&&v.r<=9&&v.r>=1&&v.c>=1&&v.c<=9&&d[v.r][v.c][v.dir]<0){///如果点有对应的方向，且下一个点未越界，且未访问过d[v.r][v.c][v.dir]=d[n2.r][n2.c][n2.dir]+1;p[v.r][v.c][v.dir]=n2;q.push(v);}}}printf("  No Solution Possible\n");
}int main(){while(cin>>s&&s!="END"){scanf("%d%d%*c%c%d%d",&r0,&c0,&d1,&r2,&c2);init();cout<<s<<endl;solve();}return 0;
}

这道题弄了好久。核心算法还是bfs，但是其中每个点多了一个分量，除了位置信息外，到该点时的朝向，所以d数组,p数组都是三元数组。紧接着就是要另外设一个has数组来判断该点是否有转弯可以转。

这道题主要还是跟着刘汝佳大神的思路走，另外参考了一下别人的代码。说说期间遇到的问题，首先是字符串“NESW”，开始没想那么多直接写成"NEWS",后来一直debug找不到问题所在。因为后面的walk函数需要就算转弯后的朝向，所以这个方向的字符串的位置要与后面求余的式子相对应，怎么写才方便呢就是时针方向。所以这里是顺时针方向。同样的turn里面也要对应上。

还有一点就是因为考虑到起点终点重合的情况，所以一开始从起点后一个位置开始(主要是has初始化过程中并没有对起点进行处理，如果从起点开始算起很麻烦)。

其次这道题，后面每一行的输入时参考别人的方法写的，学习了一种输入方式——通过getchar getline stringstream，（不过每次传完值进stringstream后要记得clear()）提取一个字符串中对应格式的信息。当然还有strchr用来查询对应字符的下标，这样可以很方便地将字符转换成对应的数值。（这个方法很实用呢感觉）；

这篇关于uva816 abbots的复仇 bfs+方向朝向的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---