UVa-816 Abbott's Revenge

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 struct Node
  6 {
  7     int r;
  8     int c;
  9     int dir;
 10     Node(int r0,int c0,int dir0) : r(r0),c(c0),dir(dir0) {}
 11     Node() {}
 12 };
 13 
 14 const char* dirs = "NESW";
 15 const char* turns = "FLR";
 16 int dir_id(char c) {return strchr(dirs,c) - dirs;}
 17 int turn_id(char c) {return strchr(turns,c) - turns;}
 18 
 19 const int dr[] = {-1,0,1,0};
 20 const int dc[] = {0,1,0,-1};
 21 
 22 Node walk(const Node& u,int turn)
 23 {
 24     int dir = u.dir;
 25     if(turn == 1) dir = (dir+3)%4;
 26     if(turn == 2) dir = (dir+1)%4;
 27     return Node(u.r+dr[dir],u.c+dc[dir],dir); 
 28 }
 29 
 30 int has_edge[10][10][5][5];
 31 int d[10][10][5];
 32 
 33 int r1,c1,dir;
 34 int r0,c0;
 35 int r2,c2;
 36 
 37 int maxr = 0,maxc = 0;
 38 
 39 int read()
 40 {
 41     memset(has_edge,0,sizeof(has_edge));
 42     string tmp;
 43     cin >> tmp;
 44     if(tmp == "END")
 45         return 1;
 46     cout << tmp << endl;
 47     char tmp_dir;
 48     cin >> r0 >> c0 >> tmp_dir >> r2 >> c2;
 49     dir = dir_id(tmp_dir);
 50     r1 = r0+dr[dir],c1 = c0+dc[dir];
 51 
 52     tmp.clear();
 53     int r,c;
 54     while(cin >> r && r != 0)
 55     {
 56         cin >> c;
 57         if(r > maxr)    maxr = r;
 58         if(c > maxc)    maxc = c;
 59         while(cin >> tmp)
 60         {
 61             if(tmp.size() == 1)
 62                 break;
 63             if(tmp.size()>=2)
 64                 has_edge[r][c][dir_id(tmp[0])][turn_id(tmp[1])] = 1;
 65             if(tmp.size()>=3)
 66                 has_edge[r][c][dir_id(tmp[0])][turn_id(tmp[2])] = 1;
 67             if(tmp.size()>=4)
 68                 has_edge[r][c][dir_id(tmp[0])][turn_id(tmp[3])] = 1;
 69         }
 70     }
 71     maxr ++;
 72     return 0;
 73 }
 74 
 75 int inside(int r,int c)
 76 {
 77     return r<=maxr && c<=maxc && r >= 1 && c >= 1;
 78 }
 79 
 80 Node p[10][10][5];
 81 
 82 void print_ans(Node u)
 83 {
 84     vector<Node> nodes;
 85     while(1)
 86     {
 87         nodes.push_back(u);
 88         if(d[u.r][u.c][u.dir] == 0) break;
 89         u = p[u.r][u.c][u.dir];
 90     }
 91     nodes.push_back(Node(r0,c0,dir));
 92     
 93     int cnt = 0;
 94     for(int i = nodes.size()-1;i >= 0;i --)
 95     {
 96         if(cnt % 10==0)    printf(" ");
 97         printf(" (%d,%d)",nodes[i].r,nodes[i].c);
 98         if(++cnt % 10==0)    cout << endl;
 99     }
100     if(nodes.size()%10!=0)    cout << endl;
101 }
102 
103 void solve()
104 {
105     queue<Node> q;
106     memset(d,-1,sizeof(d));
107     Node u(r1,c1,dir);
108     d[u.r][u.c][u.dir] = 0;
109     q.push(u);
110     while(!q.empty())
111     {
112         Node u = q.front();q.pop();
113         if(u.r == r2 && u.c == c2) {print_ans(u);return ;}
114         for(int i = 0;i < 3;i ++)
115         {
116             Node v = walk(u,i);
117             if(has_edge[u.r][u.c][u.dir][i] && inside(v.r,v.c)
118             && d[v.r][v.c][v.dir] < 0)
119             {
120                 d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] + 1;
121                 p[v.r][v.c][v.dir] = u;
122                 q.push(v);
123             }
124         }
125     }
126     printf("  No Solution Possible
");
127 }
128 
129 int main()
130 {
131     while(1)
132     {
133         int st = read();
134         if(st)
135             break;
136         solve();
137     }
138     return 0;
139 }
核心代码部分参考刘汝佳紫书