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){///每次传入一个字符串，结尾是""
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(){///bfs
queue<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 Possiblen");
}
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+方向朝向的全部内容，更多相关uva816内容请搜索靠谱客的其他文章。