UVA 816 Abbott's Revenge 紫书

紫书的这道题， 作者说是很重要。

但看着题解好长， 加上那段时间有别的事， 磨了几天没有动手。

最后，这道题我打了五遍以上 ，有两次被BUG卡了，找了很久才找到。

思路紫书上有，就缺少输入和边界判断两个部分。不是因为紫书，应该也不会找到这个WF题吧，所以其余思路就不说了。 一些注释在代码中有。

代码：

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <vector>

 #include <queue>

 using namespace std;

 const int MAXN = ;

 const char* dirs = "NESW";

 const char* turns = "FLR";

 int dir_id(char c) {return strchr(dirs, c)-dirs;}

 int turn_id(char c) {return strchr(turns, c)-turns;}

 const int dr[] = {-, , , };

 const int dc[] = {, , , -};

 struct Node

 {

     int r;

     int c;

     int dir;

     Node(int rr=, int cc=, int d=):r(rr), c(cc), dir(d) {}

 };

 int has_edge[MAXN][MAXN][][];

 int d[MAXN][MAXN][];//判断是否遍历过

 Node p[MAXN][MAXN][];

 int r0, c0, r1, c1, r2, c2, dir;

 Node walk(const Node& u, int turn)

 {

     int dir=u.dir;

     if(turn==)   dir = (dir+)%;//逆时针

     if(turn==)      dir = (dir+)%;//顺时针

     return Node(u.r+dr[dir], u.c+dc[dir], dir);

 }

 bool inside(int r, int c)//判断是否出界

 {

     return r>= && r<= && c>= && c<=;

 }

 bool read_case()

 {

     char s1[], s2[];//储存名字, 储存方向

     if(scanf("%s%d%d%s%d%d", s1, &r0, &c0, s2, &r2, &c2)!=)   return false;//输入不正确

     printf("%s\n", s1);

     memset(has_edge, , sizeof(has_edge));

     dir = dir_id(s2[]);

     r1 = r0+dr[dir];

     c1 = c0+dc[dir];

     for(; ;)

     {

         int r, c;

         scanf("%d", &r);

         if(r==)   break;

         scanf("%d", &c);

         while(scanf("%s", s2)== && s2[]!='*')

         {

             int len=strlen(s2);

             for(int i=; i<len; i++)

                 has_edge[r][c][dir_id(s2[])][turn_id(s2[i])]=;//将可走的地方赋1

         }

     }

     return true;

 }

 void print_ans(Node u)

 {

     vector<Node> nodes;

     for(; ;)//输入

     {

         nodes.push_back(u);

         if(d[u.r][u.c][u.dir]==)   break;

         u = p[u.r][u.c][u.dir];

     }

     nodes.push_back(Node(r0, c0, dir));//起点存入

     int cnt=;

     for(int i=nodes.size()-; i>=; i--)//倒着输出

     {

 //        cout<<"#i"<<endl;

         if(cnt% == )   printf(" ");

         printf(" (%d,%d)", nodes[i].r, nodes[i].c);

         if(++cnt %  ==)   printf("\n");

     }

     if(nodes.size()%!=)   printf("\n");

 }

 void solve()

 {

     queue<Node> q;

     memset(d, -, sizeof(d));

     Node u(r1, c1, dir);

     d[u.r][u.c][u.dir]=;

     q.push(u);

     while(!q.empty())

     {

         Node now = q.front();   q.pop();

         if(now.r==r2 && now.c==c2)

         {

             print_ans(now);

             return;

         }

         for(int i=; i<; i++)

         {

             Node v = walk(now, i);

             if(has_edge[now.r][now.c][now.dir][i] && d[v.r][v.c][v.dir]< && inside(v.r, v.c))

             {

                 d[v.r][v.c][v.dir] = d[now.r][now.c][now.dir]+;

                 p[v.r][v.c][v.dir] = now;

                 q.push(v);

             }

         }

     }

     printf("  No Solution Possible\n");

 }

 int main()

 {

     while(read_case())

         solve();

     return ;

 }

毕竟完成了一题WF题，虽然开始的思路不是自己想的，但还是感觉有一丝丝成就感，哈哈。