前言
正好今天在等面试= =学弟让我帮忙做一下题解，我就在这里写好啦。这也是我的第一篇博客=w=
我觉得我省赛的水平还是没问题的，第六届第七届我都是吉林省第二名，当然省赛的题目本身对算法的考察度不高。。。很暴力的那种= =
这篇题解针对的是对算法了解不深的同学们=w= 所以对于dalao们来说，这篇题解可能过于简单←_←
（博客分类竟然没有算法= =）
填空题区：
结果填空题：要求选手根据题目描述直接填写结果。求解方式不限。不要求源代码。
把结果填空的答案直接通过网页提交即可，不要书写多余的内容。
填空题注重的就是效率，快速的解决你可以做出来的所有题目。并且做的时候要仔细，毕竟结果错了分就没了= =
遇到不会的题想个四五分钟，还不会就跳过吧，等做完了会的再回头做（有点像高考？。？）因为题目，并不是按照难度排序的= =（是不是很坑）
第一题
题目
标题：迷宫
X星球的一处迷宫游乐场建在某个小山坡上。
它是由10x10相互连通的小房间组成的。
房间的地板上写着一个很大的字母。
我们假设玩家是面朝上坡的方向站立，则：
L表示走到左边的房间，
R表示走到右边的房间，
U表示走到上坡方向的房间，
D表示走到下坡方向的房间。
X星球的居民有点懒，不愿意费力思考。
他们更喜欢玩运气类的游戏。这个游戏也是如此！
开始的时候，直升机把100名玩家放入一个个小房间内。
玩家一定要按照地上的字母移动。
迷宫地图如下：
------------
UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR
------------
请你计算一下，最后，有多少玩家会走出迷宫?
而不是在里边兜圈子。
请提交该整数，表示走出迷宫的玩家数目，不要填写任何多余的内容。
如果你还没明白游戏规则，可以参看一个简化的4x4迷宫的解说图：
分析
（直升机拉100人，大吉大利今晚吃鸡！（手动斜眼笑））
最简单的方法，就是把每个点走一遍，检验一下他会不会出去。
不过这个方法麻烦的地方就是，你需要用一个辅助的表格去记录这个点有没有被走过。这样你才能确定这个点是否走进了一个死胡同里。
类似这样的
如果你多走几个点，你就会发现一个显然的结论：一个点如果能走出去，那么所有能到达这个点的点都能走出去。
那么现在你只需要倒推就好了。从那些能走出去的点开始，倒推哪些点能走到它。这样，你就不需要走每个点的时候都记录一遍了。
这种做法足以支持你快速的求出答案，当然如果你一眼就看出了这种规律，恰好你的编程能力有很强，那么你完全可以用代码代替你的人力去完成这个任务。实际上敲代码比用手画慢一些，所以这种基础的题，我建议直接用手画，毕竟时间是宝贵的。
当然如果迷宫超级大，代码的力量就体现出来了。
我还是写一份代码吧= =（实际比赛的时候我就是用第一种方法+代码完成的）
代码及运行结果
第二种方法（为什么先写第二种呢，因为写起来的话第二种比较复杂）：
#include <cstdio>#include <algorithm>
#include <queue>
using namespace std;
#define fi first
#define se second
#define pr make_pair
typedef pair<int, int> pii;
const int MAX_N = 1e1 + 5; // 对题目中出现的数据范围，可以用这种方法表示，避免重复使用时出错
// XeY 表示X * 10 ^ Y 也就是X乘以10的Y次方
// +5 是为了防止数据溢出而额外开的空间
const int d[5][3] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const char able[5] = "ULDR"; // 确定常量，方便书写
bool exitable[MAX_N][MAX_N];
char mp[MAX_N][MAX_N];
queue<pii> que;
int main() {
int ans = 0;
for (int i = 0; i < 10; i++) {
scanf("%s", mp[i]);
}
for (int j = 0; j < 10; j++) {
if (!exitable[0][j] && mp[0][j] == 'U') {
que.push(pr(0, j));
exitable[0][j] = true;
}
if (!exitable[9][j] && mp[9][j] == 'D') {
que.push(pr(9, j));
exitable[9][j] = true;
}
if (!exitable[j][0] && mp[j][0] == 'L') {
que.push(pr(j, 0));
exitable[j][0] = true;
}
if (!exitable[j][9] && mp[j][9] == 'R') {
que.push(pr(j, 9));
exitable[j][9] = true;
}
}
// 下面的这种写法被称之为广度优先搜索
while (!que.empty()) {
ans++;
int x = que.front().fi, y = que.front().se;
que.pop();
for (int i = 0; i < 4; i++) {
int tx = x + d[i][0], ty = y + d[i][1];
if (tx < 0 || tx > 9) continue;
if (ty < 0 || ty > 9) continue;
if (exitable[tx][ty]) continue;
if (mp[tx][ty] == able[i]) {
exitable[tx][ty] = true;
que.push(pr(tx, ty));
}
}
}
printf("\nans = %d\n\n", ans);
// 检验结果正确性
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (exitable[i][j]) printf("%c", mp[i][j]);
else printf("*");
}
printf("\n");
}
return 0;
}
确实很长啊= =不过这也体现了写代码的好处：方便检查（我写这种方法的时候还写错了一个地方）
运行结果：
第一种方法：
#include <cstdio>#include <algorithm>#include <set>using namespace std;#define fi first#define se second#define pr make_pairtypedef pair<int, int> pii;const int MAX_N = 1e1 + 5; // 对题目中出现的数据范围，可以用这种方法表示，避免重复使用时出错 // XeY 表示X * 10 ^ Y 也就是X乘以10的Y次方 // +5 是为了防止数据溢出而额外开的空间bool exitable[MAX_N][MAX_N];char mp[MAX_N][MAX_N];set<pii> visit;int main() { int ans = 0; for (int i = 0; i < 10; i++) { scanf("%s", mp[i]); } for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { visit.clear(); for (int x = i, y = j; true; ) { if (visit.find(pr(x, y)) != visit.end()) break; if (x < 0 || x > 9) { ans++; exitable[i][j] = true; break; } if (y < 0 || y > 9) { ans++; exitable[i][j] = true; break; } visit.insert(pr(x, y)); if (mp[x][y] == 'L') y--; else if (mp[x][y] == 'R') y++; else if (mp[x][y] == 'U') x--; else if (mp[x][y] == 'D') x++; } } } printf("\nans = %d\n\n", ans); // 检验结果正确性 for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { if (exitable[i][j]) printf("%c", mp[i][j]); else printf("*"); } printf("\n"); } return 0;}
运行结果：
（还是动手画最方便呀！）
第二题
题目
标题：跳蚱蜢
如图 所示：
其中8只盘子内装着8只蚱蜢，有一个是空盘。
我们把这些蚱蜢顺时针编号为 1~8
每只蚱蜢都可以跳到相邻的空盘中，
也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。
请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，
并且保持空盘的位置不变（也就是1-8换位，2-7换位,...），至少要经过多少次跳跃？
注意：要求提交的是一个整数，请不要填写任何多余内容或说明文字。
分析
这下貌似不能动手画了，因为这些蚂蚱可能出现的状态有9！=362880种。。。
只好写代码啦~
由于状态总数是362880种，对于计算机来说so easy，所以我们就采用暴力搜索的方式（也就是模拟动手画）。
但是要找到最少的跳跃步数，怎么办呢？
这时候就需要广度优先搜索啦（还记得上一题第二种方法里的代码吗）。
广度优先搜索有一个好处，那就是在它找到答案的时候，一定是使用了最少的步数找到的。
所以我们写一个广搜解决掉这道题就好啦。
代码及运行结果
#include <cstdio>#include <string>#include <queue>#include <map>using namespace std;#define fi first#define se second#define pr make_pairtypedef pair<string, int> psi;const string st = "012345678";const string ed = "087654321";const int d[5] = {1, 2, 7, 8};queue<pair<psi, int> > que;map<string, string> parent;int main() { // 将一个状态用string和字符0在该string中的位置来表示 // 一个状态还会附加上步数 int ans; parent[st] = ""; que.push(pr(pr(st, 0), 0)); while (!que.empty()) { string x = que.front().fi.fi; int pos = que.front().fi.se; int length = que.front().se; if (x == ed) { ans = length; break; } que.pop(); for (int i = 0; i < 4; i++) { string y = x; swap(y[pos], y[(pos + d[i]) % 9]); if (parent.count(y) == 0) { parent[y] = x; que.push(pr(pr(y, (pos + d[i]) % 9), length + 1)); } } } printf("ans = %d\n\n", ans); // 打印蚂蚱跳跃的路径 for (string now = ed; now != ""; now = parent[now]) { printf("%s\n", now.c_str()); } return 0;}
从代码中可以看出，广搜的代码实现一般是这个样子的：
（1）将初始状态放入一个记录状态的queue
（2）不断地取出queue中的状态直至空
（3）每取出一个状态，遍历它所有可以到达的合法状态，并将其装入queue
运行结果（路径是倒过来印的，其实没有区别，蚂蚱可以跳过来就可以跳回去）：
那么问题来了，怎么检验正确性呢？
在检验代码正确无误后（或者错误就是发现不了）后，我没有别的办法= =（动手画太难啦！），所以我到现在也不知道这个答案对不对。
当然，如果我们时间充足，我们可以用另一种方法实现，实际上，这种方法并不是一种高效的方法。但是一般情况下，做到这里就足够了。所以比赛的时候我推荐用这种方法。
拓展
我们可以发现广搜的运行就像一个三角洲，一条小河慢慢汇入大海那样：
这导致搜索的状态会越来越多，例如这道题，每一种状态有4种转移方式（其中两种是镜像），也就是说，状态数随着步数呈指数级增长。那么怎么减少状态数呢？
我们不仅知道起始状态，还知道终止状态。那么我们从两头同时广搜，结果就会少很多了=w=：
#include <cstdio>#include <string>#include <queue>#include <map>using namespace std;#define fi first#define se second#define pr make_pairtypedef pair<string, int> psi;const string st = "012345678";const string ed = "087654321";const int d[5] = {1, 2, 7, 8};queue<pair<psi, int> > que;map<string, int> length[2];int main() { // 将一个状态用string和字符0在该string中的位置来表示 // 一个状态还会附加上该状态属于哪种状态 // 0 代表 从st出发；1 代表 从ed出发 int ans; length[0][st] = 0; length[1][ed] = 0; que.push(pr(pr(st, 0), 0)); que.push(pr(pr(ed, 0), 1)); while (!que.empty()) { string x = que.front().fi.fi; int pos = que.front().fi.se; int kind = que.front().se; if (length[1 - kind].count(x) != 0) { ans = length[0][x] + length[1][x]; break; } que.pop(); for (int i = 0; i < 4; i++) { string y = x; swap(y[pos], y[(pos + d[i]) % 9]); if (length[kind].count(y) == 0) { length[kind][y] = length[kind][x] + 1; que.push(pr(pr(y, (pos + d[i]) % 9), kind)); } } } printf("ans = %d\n\n", ans); return 0;}
运行结果：
（侧面印证了我的方法是对的）
当然了，比赛的时候效率最重要，这种题用普通的广搜就已经可以完美解决啦！