Abbott's Revenge

题目传送阵
大致题意：一个最多包涵9*9个节点的迷宫，横纵节点下标1-9，输入迷宫名，起点位置，离开起点时的方向和终点位置，每个节点进入方向和对应的转换方向，求一条到终点的最短路
分析：
1.将输入信息存储，以 zhuan[x][y][进入方向][转换方向] 记录每个节点的出入
2.定义行走的函数、转向函数、判断当前转向行走是否可行函数
3.从起点开始bfs
以队列queue，从起点开始逐步扩大路长，寻找终点
注：1.每次走到节点，就将该位置方向 road[x][y][方向]=1；避免重复行走
注：2.节点只有输入的起始点，终点、换向点，没有其他节点
注：3.当下一步行走可行时，把当前节点作为下一个节点的父节点（便于最后输出迷宫行走路线）
4.从终点开始，回溯路线，输出结果

#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int x1,y1,x2,y2,x,y,road[10][10][4],zhuan[10][10][4][4];
char c,s[10];string name;
int dir_x[]={-1,0,1,0};
int dir_y[]={0,1,0,-1};
char fangxiang[]="NESW";
char turn[]="FRL";
int dir_id(char &c){return strchr(fangxiang,c)-fangxiang;}
int turn_id(char &c){return strchr(turn,c)-turn;}
struct Node
{
int x,y,dir;
Node(int x1,int y1,int dir1):x(x1),y(y1),dir(dir1){}
Node():x(0),y(0),dir(-1){}
}father[10][10][4];
void read()
{
memset(road,0,sizeof(road));
memset(zhuan,0,sizeof(zhuan));
scanf("%d%d %c%d%d",&x1,&y1,&c,&x2,&y2);
int dir=dir_id(c);
road[x1][y1][dir]=-1;
zhuan[x1][y1][dir][0]=1;
while(scanf("%d",&x)&&x)//路口输入 
{
scanf("%d",&y);
while(scanf("%s",s)&&s[0]!='*')
{
int d=dir_id(s[0]);
for(int i=1;i<strlen(s);++i)
{
zhuan[x][y][d][turn_id(s[i])]=1;
}
}
}
}
Node walk(const Node& u,int &i)
{
int dir=u.dir;
if(i==1) dir=(1+dir)%4;
else if(i==2) dir=(dir+3)%4;
return Node(u.x+dir_x[dir],u.y+dir_y[dir],dir);
}
bool zhuan1(const Node& u,const Node& v,const int& i)
{
if(v.x<0||v.x>9||v.y<0||v.y>9) {return false;}//越界 
if(road[v.x][v.y][v.dir]!=0) {return false;}//重复经过node ,road[][][]原点=0； 
if(zhuan[u.x][u.y][u.dir][i]==0) {return false;}
return true;
}
void print_road(Node &u)
{
vector<Node>w;
while(1)
{
if(road[u.x][u.y][u.dir]==-1)
{
w.push_back(u);break;
}
w.push_back(u);
u=father[u.x][u.y][u.dir];
}
int cnt=0;
for(int i=w.size()-1;i>=0;--i)
{
if(cnt%10==0) printf(" ");
printf(" (%d,%d)",w[i].x,w[i].y);
if(++cnt%10==0) printf("n");
}
if(w.size()%10!=0) printf("n");
}
void bfs()
{
queue<Node>q;
Node u(x1,y1,dir_id(c));
q.push(u);
while(!q.empty())
{
Node t=q.front();
q.pop();
if(t.x==x2&&t.y==y2)
{
print_road(t);return;
}
for(int i=0;i<3;++i)
{
Node v=walk(t,i);
if(zhuan1(t,v,i))
{
road[v.x][v.y][v.dir]=1;
father[v.x][v.y][v.dir]=t;
q.push(v);
}
}
}
printf("
No Solution Possiblen");
}
int main()
{
while(cin>>name&&name!="END")
{
read();
cout<<name<<endl;
bfs();
}
}

最后

以上就是老实帅哥为你收集整理的Abbott's Revenge的全部内容，希望文章能够帮你解决Abbott's Revenge所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。