J - Abbott's Revenge 搜索 寒假训练

题目

题目大意：
这个题目就是大小不超过9*9的迷宫，给你起点终点和起点的方向，让你进行移动
移动特别之处是不一定上下左右都可以，只有根据方向确定可以走的方向。
思路：
需要写一个读入函数，这个需要读入起点，终点，方向（简单），还有就是接下来几行的不同位置
可以转的方向，可以写几个函数，根据函数来判断方向，最后转换成数字，用bool类型数组0，1分别代表
可以或不可以。
之后要写一个bfs，这个比较简单，就是和普通差不多，但是之后要输出路线，所以
要有两个数组，一个用来存储路程，一个用来存储路线。
具体一点的bfs，就是先把初始位置放进去，写清楚距离，之后进去while，while里面要有一个判断
是否到了终点，之后就用walk函数进行走路，然后判断这一步是否合法，合法就走下一步，不过，走下一步之前，记住两个点
第一个就是去记录距离，第二个就是记录路线。
最后有一个输出函数，用vector

总的来说，这也是一个最短路问题，和robot有点像，就是每个位置不一定每个方向都是对的。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
string name;
int x1,x2,y1,y2,dir,x,y;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
const char *dirs="ESWN";
const char *turns="FLR";
const int maxn=100;
bool has_edge[maxn][maxn][10][10];
int d[maxn][maxn][4];
int dir_id(char c)
{
return (strchr(dirs,c)-dirs);
}
int turn_id(char c)
{
return (strchr(turns,c)-turns);
}
struct node
{
int x,y,dir;
node(int x=0,int y=0,int dir=0):x(x),y(y),dir(dir){}
}b[maxn][maxn][4];
node walk(const node& u,int turn)
{
int dir=u.dir;
if(turn==1) dir=(dir+3)%4;
if(turn==2) dir=(dir+1)%4;
return node(u.x+dx[dir],u.y+dy[dir],dir);
}
bool scan()
{
memset(has_edge,0,sizeof(has_edge));
cin>>name;
if(name=="END") return false;
char s[100];
cin>>x>>y>>s>>x2>>y2;
dir=dir_id(s[0]);
x1=x+dx[dir];
y1=y+dy[dir];
int r,c;
while(cin>>r)
{
if(r==0) break;
cin>>c;
char s1[100];
while(cin>>s1)
{
if(s1[0]=='*') break;
int l=strlen(s1);
for(int i=1;i<l;i++)
{
has_edge[r][c][dir_id(s1[0])][turn_id(s1[i])]=1;
// printf("has_edge[%d][%d][%d][%d]=1;n",r,c,dir_id(s1[0]),turn_id(s1[i]));

}
}
}
cout<<name<<endl;
return true;
}
bool judge(int r, int c)
{
return r >=1 && r <= 9 && c >= 1 && c <= 9;//迷宫从1开始
}
void print_ans(node exa)
{
vector<node>nodes;
while(true)
{
nodes.push_back(exa);
if(d[exa.x][exa.y][exa.dir]==0) break;
exa=b[exa.x][exa.y][exa.dir];
}
nodes.push_back(node(x,y,dir));
int cnt=0;
for(int i=nodes.size()-1;i>=0;i--)
{
if(cnt%10==0) printf(" ");
cnt++;
printf(" (%d,%d)",nodes[i].x,nodes[i].y);
if(cnt%10==0) printf("n");
}
if(cnt%10!=0) printf("n");
}
void bfs()
{
queue<node>que;
node exa=node(x1,y1,dir);
memset(d,-1,sizeof(d));
d[exa.x][exa.y][exa.dir]=0;
que.push(exa);
while(!que.empty())
{
node exa=que.front();
//printf("%d %d %dn",exa.x,exa.y,exa.dir);

que.pop();
if(exa.x==x2&&exa.y==y2)
{
print_ans(exa);
return ;
}
for(int i=0;i<3;i++)
{
node v=walk(exa,i);
//
printf("www %d %d %d %dn",v.x,v.y,v.dir,i);
//
printf("d[%d][%d][%d]=%dn",v.x,v.y,v.dir,d[v.x][v.y][v.dir]);
if(has_edge[exa.x][exa.y][exa.dir][i]&&judge(v.x,v.y)&&d[v.x][v.y][v.dir]<0)
{
d[v.x][v.y][v.dir]=d[exa.x][exa.y][exa.dir]+1;
b[v.x][v.y][v.dir]=exa;
//printf("%d %d %dn",v.x,v.y,v.dir);

que.push(v);
}
}
}
printf("
No Solution Possiblen");
}
int main()
{
while(scan())
{
bfs();
}
return 0;
}