第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-161 Abbott’s Revenge(C++写法)
前言
这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都会有几种语言的写法，帮助大家提供一个思路，当然，思路只是思路，千万别只看着答案就认为会了啊，这个方法基本上很难让你成长，成长是在思考的过程中找寻到自己的那个解题思路，并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练，如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢，这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来，所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式，说着听绕口，但是就是靠量来堆叠思维方式，刷题方案自主定义的话肯定就是从非常简单的开始，稍微对数据结构有一定的理解，暴力、二分法等等，一步步的成长，数据结构很多，一般也就几种啊，线性表、树、图、再就是其它了。顺序表与链表也就是线性表，当然栈，队列还有串都是属于线性表的，这个我就不在这里一一细分了，相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的，例如三分枚举、离散化，图，复杂数据结构还有统计都是不考的，我们找简单题刷个一两百，然后再进行中等题目的训练，当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠，慢慢的就会掌握各种规律，有了规律就能大胆的长一些难度比较高的题目了，再次说明，刷题一定要循序渐进，千万别想着直接就能解决难题，那只是对自己进行劝退处理。加油，平常心，一步步前进。
Abbott’s Revenge
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
在1999年的World Finals中有一个基于Dice Maze(骰子迷宫)的题目。在出题人编写那道题目的时候，他们并没有发现这种迷宫的创意来源。然而在那场比赛结束不久，创作了大量的这种迷宫的Robert Abbott先生，联系了比赛主办方并确认自己是骰子迷宫的原作者。我们很遗憾没有在去年的题目描述中感谢Abbott先生的原创意，但我们很高兴Abbott先生主动为今年的比赛提供他原创的、未公开的“步行通过的箭头迷宫”。
与大多数的迷宫相同，箭头迷宫也是每次从一个路口走到另一个路口，直到到达终点。在每个路口处，如果你从某个方向进入了该路口，那么路口的地面上在靠近你的方向会画有一组箭头，它们相对于你的方向可以是向左，向前，向右，或者是它们的任意组合。
图1描述了一个箭头迷宫。每个路口用二维坐标(x,y)表示，以左上角的路口为(1,1)。在图1给出的迷宫中，起点的坐标是(3,1)，终点的坐标是(3,3)。在你开始后，你只能向北走1步到达(2,1)。由于你是从南边到达(2,1)这一点的，而这一点在南边的箭头是向前指的，所以你只能继续向前走到达(1,1)。在此之后，由于你是从南边到达了(1,1)，这一点在南边的箭头是向右指的，所以你也只能向右拐，到达(1,2)。到目前为止，你还没有做出任何选择。以此类推，你会接着依次经过(2,2) (2,3) (1,3) (1,2)。现在你可以选择继续向前走或者向左转。如果你向前走，你会回到(1,1)，而向左转可以让你到达(2,2)。事实上，唯一最优的方案是依次经过以下路口：(3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1) (2,2) (1,2) (1,3) (2,3) (3,3)。
你需要写一个程序解决这个迷宫。“解决”的意义是：只要迷宫是可解的，你就要找到一条路线，它必须在起点沿指定的方向走出，并最终到达终点，当然，路线的长度需要是所有方案中最短的。
输入格式
输入文件包括一个或多个箭头迷宫。每个迷宫描述的第一行是这个迷宫的名称，保证它只由数字和字母组成且长度不超过20。接下来的一行依次包含了起点的坐标，起始时方向，目标点的坐标，以空格隔开。本题的迷宫最大尺寸为9×9，所以行与列的编号均为1到9。起始时的方向为N,S,E,W之一，分别代表北、南、西、东。
剩下的若干行按照以下格式输入：一对整数，若干字符串，以星号(*)结束，以空格隔开。每一行代表一个路口，一对整数表示路口的坐标。对于每一个字符串，第一位为N,S,E,W之一，接下来若干位只可能包含L,F,R，分别代表向左，向前，向右。这个字符串的含义是：朝向某个方向进入该路口(所以箭头被画在这个路口的相反方向)，接下来就只能向某个方向继续行走。
对于每个迷宫，以0作为一行的结束，从接下来一行开始就是一个新的箭头迷宫。输入文件以单独的一行END作为结尾。
输出格式
对于每个箭头迷宫，应该先输出它的名字，然后接下来若干行，输出一个路径，格式如问题描述中所述；或者输出"No Solution Possible"。迷宫的名字应从第1列开始，而其余所有的行都从第3列开始，即行首有2个空格。对于输出的每个路径，除最后一行外，每行须输出恰好10个路口(坐标)。
在下面的样例中，输入的第一个迷宫是图1中的迷宫。
注意，在下面的样例输出当中，除了SAMPLE和NOSOLUTION两行以外，其余的行首都需要空两格！（由于格式化问题未能显示出来）
样例输入
SAMPLE
3 1 N 3 3
1 1 WL NR *
1 2 WLF NR ER *
1 3 NL ER *
2 1 SL WR NF *
2 2 SL WF ELF *
2 3 SFR EL *
0
NOSOLUTION
3 1 N 3 2
1 1 WL NR *
1 2 NL ER *
2 1 SL WR NFR *
2 2 SR EL *
0
END
样例输出
SAMPLE
(3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1)
(2,2) (1,2) (1,3) (2,3) (3,3)
NOSOLUTION
No Solution Possible
数据规模和约定
设T为数据组数：对于30%的数据，T=1；对于60%的数据，T≤100；对于100%的数据，T≤1000。
题解：
C++语言
#include<stdio.h> #include<string.h> #include<iostream> #include<queue> #include <algorithm> using namespace std; struct Node { int r, c, dir; Node(int r=0, int c=0, int dir=0):r(r),c(c),dir(dir) {} }; const int dr[] = { -1, 0, 1, 0 }; const int dc[] = { 0, 1, 0, -1 }; 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; } bool inside(int r, int c) { return r >= 1 && r <= 9 && c >= 1 && c <= 9; } Node walk(Node u, int turn) { int dir = u.dir; if(turn == 1) dir = (dir + 3) % 4; if(turn == 2) dir = (dir + 1) % 4; return Node(u.r + dr[dir], u.c + dc[dir], dir); } const int maxn = 10; int dir, r0, c0, r1, c1, r2, c2; int has_edge[maxn][maxn][4][3]; bool read_case() { char s[99], s2[99]; if(scanf("%s%d%d%s%d%d", s,&r0, &c0, s2, &r2, &c2) != 6) return false; printf("%s\n", s); dir = dir_id(s2[0]); r1 = r0 + dr[dir]; c1 = c0 + dc[dir]; memset(has_edge, 0, sizeof(has_edge)); for(;;) { int r, c; scanf("%d", &r); if(r == 0) break; scanf("%d", &c); while(scanf("%s", s) == 1 && s[0] != '*') { for(int i = 1; i < strlen(s); ++i) has_edge[r][c][dir_id(s[0])][turn_id(s[i])] = 1; } } return true; } int d[maxn][maxn][4]; Node p[maxn][maxn][4]; void print_ans(Node u) { vector<Node> nodes; for(;;) { nodes.push_back(u); if(d[u.r][u.c][u.dir] == 0) break; u = p[u.r][u.c][u.dir]; } nodes.push_back(Node(r0, c0, dir)); int cnt = 0; for(int i = nodes.size()-1; i >= 0; --i) { if(cnt%10 == 0) printf(" "); printf(" (%d,%d)", nodes[i].r, nodes[i].c); if(++cnt % 10 == 0) printf("\n"); } if(nodes.size() % 10 != 0) printf("\n"); } void solve() { queue<Node> q; memset(d, -1, sizeof(d)); Node u(r1, c1, dir); d[r1][c1][dir] = 0; q.push(u); while(!q.empty()) { Node 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) { d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] + 1; p[v.r][v.c][v.dir] = u; q.push(v); } } } printf(" No Solution Possible\n"); } int main() { while(read_case()) { solve(); } return 0; }
总结
没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
