是典型的bfs，但是，这个问题的目的在于读取条件的困难，而不是简单地推断，需要找到一种方法来读取条件。还需要想办法去推断每一点不能满足条件，继续往下走。
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std; struct note
{
int r;
int c;
int dir;
};
string s,s1;
int r0,c0,r1,c1,dir,r2,c2;
int has_edge[10][10][4][3];
int d[10][10][4];
note p[10][10][4];
char dirs[]={'N','E','S','W'};
char turns[]={'F','L','R'};
int dr[]={-1,0,1,0};
int dc[]={0,1,0,-1}; note walk(note u,int turn)
{
note v;
int dirr=u.dir;
if(turn==1) {dirr=(dirr+3)%4;}
if(turn==2) {dirr=(dirr+1)%4;}
v.r=u.r+dr[dirr];
v.c=u.c+dc[dirr];
v.dir=dirr;
return v;
}
bool inside(int x,int y)
{
if(x>=1&&x<=9&&y>=1&&y<=9) return true;
return false;
}
void print_ans(note u)
{
vector<note> vec;
while(1)
{
if(d[u.r][u.c][u.dir]==0) break;
vec.push_back(u);
u=p[u.r][u.c][u.dir];
}
u.r=r0;u.c=c0;u.dir=dir;
vec.push_back(u);
cout<<s1<<endl;
int cnt=0;
for(int i=vec.size()-1;i>=0;i--)
{
cnt++;
if(cnt==1) printf(" ");
printf("(%d,%d)",vec[i].r,vec[i].c);
if(cnt!=10&&i!=0) printf(" ");
if(cnt==10&&i!=0) {printf("\n");cnt=0;}
}
printf("\n");
}
void solve()
{
queue<note> q;
note uu;
uu.r=r0;uu.c=c0;uu.dir=dir;
note u;
u.r=r1;u.c=c1;u.dir=dir;
d[r1][c1][dir]=1;
p[r1][c1][dir]=uu;
d[r0][c0][dir]=0;
q.push(u);
while(!q.empty())
{
u=q.front();
q.pop();
if(u.r==r2&&u.c==c2) {print_ans(u);return;}
for(int i=0;i<3;i++)
{
note v=walk(u,i);
if(has_edge[u.r][u.c][u.dir][i]&&inside(v.r,v.c)&&d[v.r][v.c][v.dir]<0)
{
p[v.r][v.c][v.dir]=u;
d[v.r][v.c][v.dir]=d[u.r][u.c][u.dir]+1;
q.push(v);
}
}
}
cout<<s1<<endl;
printf(" No Solution Possible\n");
} int main()
{
while(cin>>s1)
{
if(s1=="END") break;
memset(has_edge,0,sizeof(has_edge));
memset(d,-1,sizeof(d));
memset(p,0,sizeof(p));
int a,count=0;
int a1,a2,dir1,turn1;
while(cin>>a)
{
if(a==0) break;
count++;
if(count==1)
{
r0=a;
cin>>c0>>s>>r2>>c2;
for(int i=0;i<4;i++)
{
if(s[0]==dirs[i])
{
dir=i;
break;
}
}
r1=r0+dr[dir];
c1=c0+dc[dir];
}
else
{
a1=a;
cin>>a2;
while(cin>>s)
{
if(s[0]=='*') break;
for(int i=0;i<4;i++)
{
if(s[0]==dirs[i])
{
dir1=i;
break;
}
}
for(int i=1;i<s.size();i++)
{
for(int j=0;j<3;j++)
{
if(s[i]==turns[j])
{
turn1=j;
break;
}
}
has_edge[a1][a2][dir1][turn1]=1;
}
}
}
}
// for(int i=1;i<=9;i++)
// {
// for(int j=1;j<=9;j++)
// {
// for(int k=0;k<4;k++)
// {
// for(int l=0;l<3;l++)
// {
// if(has_edge[i][j][k][l])
// printf("[%d][%d][%d][%d]\n",i,j,k,l);
// }
// }
// }
// }
solve();
}
return 0;
}
在解决这道题目的过程中，用到了一些非常好的处理问题的方法，也包括了一些处理问题的小细节，这样的题的解题思想，方法国。还有一些细节要掌握应该有。
版权声明：请注明出处撒...http://blog.csdn.net/u013382399