uva 816
///
/// BFS
///BFS
///
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
using namespace std;
const char* dirs="NESW";
const char* turns="FLR";
const int dr[]={-1,0,1,0};
const int dc[]={0,1,0,-1};
struct Node
{
int r;
int c;
int dir;
};
string s1, s2;
int r0,c0,r1,c1,dir,r2,c2;
int has_edge[10][10][4][3];
int d[10][10][4];
Node p[10][10][4];
///int dir_id(char c) {return strchr(dirs,c)-dirs};
///int turn_id(char c) {return strchr(turns,c)-turns};
bool inside(int a, int b)
{
if(a>0&&a<10&&b>0&&b<10)
return true;
return false ;
}
Node walk(Node &u,int turn)
{
Node 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;
}
void print_ans(Node &u)
{
vector<Node> 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("
");cnt=0;}
}
printf("
");
}
void solve()
{
queue<Node> q;
Node uu;
uu.r=r0;uu.c=c0;uu.dir=dir;
Node 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++)
{
Node 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
");
}
int main()
{
while(cin>>s1 && s1!="END")
{
memset(has_edge,0,sizeof(has_edge));
memset(d,-1,sizeof(d));
memset(p,0,sizeof(p));
int temp, cnt=0;
while(cin>>temp)
{
if(temp==0) break;
cnt++;
if(cnt==1)
{
r0=temp;
cin>>c0>>s1>>r2>>c2;
for(int i=0; i<4; i++)
{
if(s1[0]==dirs[i])
{
r1=r0+dr[i];
c1=c0+dc[i];
}
}
}
///int R,C,t1,t2;
else
{
int R,C,t1;
R=temp;
cin>>C;
while(cin>>s2&&s2!="*")
{
for(int i=0; i<4; i++)
if(s2[0]==dirs[i])
{
t1=i;
break;
}
for(int i=1; i<s2.size(); i++)
{
for(int j=0; j<3; j++)
if(s2[i]==turns[j])
has_edge[R][C][t1][j]=1;
}
}
}
}
solve();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
ACM - 계산 기하학 적 Pick - up sticks -- poj 2653Description Stan has n sticks of various length. The data for each case start with 1 <= n <= 100000, the number of stick...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.