UVa 816 - Abbott's Revenge

63 阅读 0 评论 42 点赞

我是靠谱客的博主帅气牛排，最近开发中收集的这篇文章主要介绍UVa 816 - Abbott's Revenge，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目内容见：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=757

这里贴出自己加了注释的代码，应该比较好理解了。源代码参考紫书

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<vector>
  4 #include<queue>
  5 using namespace std;
  6 
  7 struct Node {
  8   int r, c, dir; // 站在(r,c)，面朝方向dir(0~3分别表示N, E, S, W)
  9   Node(int r=0, int c=0, int dir=0):r(r),c(c),dir(dir) {}//对node初始化 
 10 };
 11 
 12 const int maxn = 10;//rc的范围（0-9） 
 13 const char* dirs = "NESW"; // 顺时针旋转，进入时的朝向 
 14 const char* turns = "FLR";//允许的三个转向方向 
 15 
 16 int has_edge[maxn][maxn][4][3];//保存每一个坐标的具体转向方式，允许则为1，不允许则为0 。在(r,c)的某个方向上允许的三向操作 
 17 int d[maxn][maxn][4];//用来累加起点到终点的距离
 18 Node p[maxn][maxn][4];//p[r][c][dir]表示了(r,c,dir)在BFS树中的父节点 
 19 int r0, c0, dir, r1, c1, r2, c2;
 20 
 21 int dir_id(char c) { return strchr(dirs, c) - dirs; }//返回c在dirs的位置
 22 int turn_id(char c) { return strchr(turns, c) - turns; }
 23 /*与NESW对应 例如向N，则dr-1,而dc不变*/ 
 24 const int dr[] = {-1, 0, 1, 0};
 25 const int dc[] = {0, 1, 0, -1};
 26 
 27 Node walk(const Node& u, int turn) {
 28   int dir = u.dir;
 29   //turn 为1则左转，为2则右转 
 30   if(turn == 1) dir = (dir + 3) % 4; // 逆时针，表示左转
 31   if(turn == 2) dir = (dir + 1) % 4; // 顺时针，表示右转
 32   return Node(u.r + dr[dir], u.c + dc[dir], dir);
 33 }
 34 
 35 //判断坐标是否出界
 36 bool inside(int r, int c) {
 37   return r >= 1 && r <= 9 && c >= 1 && c <= 9;
 38 }
 39 
 40 //初始化起点，终点和每一个坐标的转向
 41 bool read_case() {
 42   char s[99], s2[99];
 43   //s是指当前的流程，r0表示起始行，c0表示起始列，s2起始方向，r2表示目标行，c2表示目标列
 44   if(scanf("%d%d%s%d%d", &r0, &c0, s2, &r2, &c2) != 5) return false; //如果输入不是五个元素，则报错 
 45   dir = dir_id(s2[0]);//方向在字符串dirs中的位置，确定起始方向 
 46   r1 = r0 + dr[dir];//第一步之后的行坐标
 47   c1 = c0 + dc[dir];//第一步之后的列坐标
 48 
 49   memset(has_edge, 0, sizeof(has_edge));//将has_edge初始化为0 
 50   for(;;) {
 51     int r, c;
 52     scanf("%d", &r);
 53     if(r == 0) break;//约定输入0时表示输入完成 
 54     scanf("%d", &c);
 55     while(scanf("%s", s) == 1 && s[0] != '*') {//*是本行输入完成结束符 
 56       for(int i = 1; i < strlen(s); i++)
 57         has_edge[r][c][dir_id(s[0])][turn_id(s[i])] = 1;
 58     }
 59   }
 60   return true;//可以接着循环 
 61 }
 62 
 63 void print_ans(Node u) {
 64   // 从目标结点逆序追溯到初始结点
 65   //由此看出本题的解决思路：先通过宽度优先遍历找到终点，再回溯到原点并打印 
 66   vector<Node> nodes;
 67   for(;;) {
 68     nodes.push_back(u);
 69     if(d[u.r][u.c][u.dir] == 0) break;//说明找到了终点
 70     u = p[u.r][u.c][u.dir];//找自己的父节点 
 71   }
 72   nodes.push_back(Node(r0, c0, dir));//把起始点也放入数组中 
 73 
 74   // 打印解，每行10个
 75   int cnt = 0;
 76   for(int i = nodes.size()-1; i >= 0; i--) {
 77     printf(" (%d,%d) ", nodes[i].r, nodes[i].c);
 78     if(++cnt == 10){
 79         printf("n");
 80     }
 81   }
 82 }
 83 
 84 //使用BFS输出
 85 void solve() {
 86   queue<Node> q;
 87   memset(d, -1, sizeof(d));//初始化d为-1，d是用来累加起点到终点的距离的 
 88   //第一步之后，处于（2,1，N）的状态
 89   Node u(r1, c1, dir);//走了一步之后的坐标
 90   d[u.r][u.c][u.dir] = 0;
 91   //宽度优先遍历 
 92   q.push(u);
 93   while(!q.empty()) {
 94     Node u = q.front(); q.pop();
 95     if(u.r == r2 && u.c == c2) { print_ans(u); return; }//如果是目标位置，则打印并返回 
 96     //判断当前坐标点，在当前转向的三个方向哪个是可以行使的？实质还是遍历所有点直至终点的解法 
 97     for(int i = 0; i < 3; i++) {
 98       Node v = walk(u, i);
 99       //v是u坐标行走一步之后的坐标，走到终点没有初始化，has_edge值为0，不进入循环
100       if(has_edge[u.r][u.c][u.dir][i] && inside(v.r, v.c) && d[v.r][v.c][v.dir] < 0) {
101         d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] + 1;//累加1，最后得出起点到终点的距离
102         p[v.r][v.c][v.dir] = u;//表示v的父节点是u
103         q.push(v);
104       }
105     }
106   }
107   printf("  No Solution Possiblen");//如果遍历了所有节点也没有从上面的入口出去，则说明无解 
108 }
109 
110 int main() {
111     //read_case一次读入一个问题的输入并用solve解决 
112   while(read_case()) {
113     solve();
114   }
115   return 0;
116 }