uva 816

3712 단어 ACMuva
///                         
///        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; }

좋은 웹페이지 즐겨찾기