青蛙跳杯子详细题解
发表于更新于
字数总计2.8k阅读时长11分钟阅读量
注意
该博客是为了帮助同学学习，并非为了协助同学刷题，请读者保持自觉，请勿做CV工具人。另外为了节省篇幅，代码中不再写明#include，如果遇到我没有声明的函数，那么就是某一个头文件中的函数，读者搜索“c + 函数名字”就能查到相关信息。
题目
X 星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
X 星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
如下，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。
*WWWBBB
其中，W 字母表示白色青蛙，B 字母表示黑色青蛙，* 表示空杯子。
X 星的青蛙很有些癖好，它们只做 3 个动作之一：
- 跳到相邻的空杯子里
- 隔着 1 只其它的青蛙（随便什么颜色）跳到空杯子里
- 隔着 2 只其它的青蛙（随便什么颜色）跳到空杯子里
对于例子中的局面，只要 1 步，就可跳成下面的局面：
WWW*BBB
本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。
输入格式
输入为 2 行，2 个串，表示初始局面和目标局面。
输入的串的长度不超过 15。 数据保证只有一个空杯子。
输出格式
输出要求为一个整数，表示至少需要多少步的青蛙跳。
输入样例
WWBB
WWBB
输出样例
2
补充信息
代码长度限制：16KB
时间限制：100ms
内存限制：64MB
思路
看到这个题的第一反应是贪心，每次走最优的一步。但是随后进一步思考就发现了问题：什么是最优？这个题我们很难判断怎么走是当前的最优解。例如下面的输入：
*WWBBB
W*WBBW
靠脑子想估计都得想一会才能想出来，就别说用代码了。我们很快否定这一思路，随后不难想到使用枚举的方式，将所有可行的步骤枚举出来，找到步数最小的就是正确答案。
现在我们将问题转换成了：用什么方法枚举？
初步思考后可以得出两个方法，使用BFS（广度优先搜索）或DFS（深度优先搜索）进行搜索。现在假设我们使用DFS，那么我们应该“一路走到底”式的进行“探索”，我们可以实现的优化就是当目前步数大于最小步数却依然没有找到答案时就可以中断这个分支的搜索。再假设我们使用BFS，因为BFS是所有分支同时向下搜索，我们再每一次搜索时都可以保证所有现存状态的步数都是一样的，所以遇到的第一个答案就是步数最少的解。
很显然两者在理论层面的性能差距不怎么大（可能是BFS更优），在不同的情况下有可能BFS更优也可能DFS更优。似乎我们使用哪一个都可以，但是我们还需要考虑一个问题：代码复杂度。
首先，我们需要一个值来存储目前找到的最优解，以便我们在搜索时判断是否直接中断当前搜索。然后，我们还需要一个值来存储当前正在搜索的分支。最后，还需要有一个列表存储等待搜索的分支。
总结一下我们需要编写以下功能：
- 存储当前最优解
- 存储当前搜索节点
- 存储等待搜索的节点
- 状态去重
DFS状态去重
DFS时遇到重复的状态的话，我们很显然不能直接停止，而是需要再计算一次。所以为了节省性能，我们需要为已经走过的状态存储最优解，在遇到重复的状态的时候直接读取当前状态的最优解就可以结束这一分支的探索了。
BFS状态去重
BFS因为是所有分支同步向下探索，所以如果同步骤遇到重复的节点那么只保留一个即可，如果是当前状态和之前的某个状态重复，那么这个分支必定不能得到最优解（因为中间有步骤可以换成更少的步骤替代），直接丢弃这一分支即可。
综上所述，总体看来是BFS更容易编写，所以我们选择使用BFS。
搜索
但是又有一个非常头疼的问题冒了出来：怎么搜索？
从输入规模我们可以直到，最长的输入是14个青蛙，一个空杯子。难道我们每次搜索都要把所有青蛙可能的移动判断一遍？这样做是可以的，但是有更简单的想法。我们仔细观察以下，每一次青蛙的跳动可以看作是青蛙和空杯子交换位置，所以我们为什么不把这道题看成是移动空杯子呢？
这样一想，搜索的思路就有了，每一次遍历空杯子可能的移动就可以了。根据题意不难得出，空杯子一共有六种移动方式（遇到边界时会小于6）：
- 向左移动3格
- 向左移动2格
- 向左移动1格
- 向右移动1格
- 向右移动2格
- 向右移动3格
题解
根据上面的思路，我们可以写出这样的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61 | #include <bits/stdc++.h>
using namespace std;
const int ops[] = {-3, -2, -1, 1, 2, 3};
struct State {
string str;
int step = 0;
int empty;
explicit State(const string& data) {
str = data;
empty = data.find('*');
}
bool jump(int op) {
int toIndex = empty - op;
if (toIndex < 0 || toIndex >= str.length()) return false;
++step;
swap(str[empty], str[toIndex]);
empty = toIndex;
return true;
}
bool operator ==(const State& that) const {
return str == that.str;
}
};
map<string, bool> record;
queue<State> que;
int bfs(State& state, State& end) {
que.push(state);
record[state.str] = true;
while (!que.empty()) {
State& next = que.front();
que.pop();
for (const auto& item: ops) {
State preview(next);
if (!preview.jump(item)) continue;
if (preview == end) return preview.step;
if (!record[preview.str]) {
record[preview.str] = true;
que.push(preview);
}
}
}
return -1;
}
int main() {
string start, end;
cin >> start >> end;
if (start == end) return (printf("0"), 0);
State head(start);
State tail(end);
printf("%d", bfs(head, tail));
return 0;
}
|
查看PTA测试信息
语言：C++（G++）
结果：答案正确
最长耗时：70ms
最大内存：4012KB
注意：以上已经是完整的题解了，下面的内容是代码的优化，在竞赛中是完全没有必要的。
但是有兴趣的同学也可以看一下，可以拓宽一下自己的思路。
哈希优化
我们简单分析一下代码，不难发现很多时间花在了字符串的拷贝、判断中，我们可以想办法减少或者去掉这部分的性能花费。
通过题意，我们可以直到最多有14只青蛙，1个空杯子。可以发现，一个位置上有三种状态：黑、白、空，并且空这种情况只会出现一次。那么我们是不是可以只存储黑、白，然后单独用一个值来存储空。这样我们就把一个位置上可能的状态变成了两种：黑、白。
这时候有经验的就能看出来了，直接使用一个int就可以存储这个列表了。同时我们规定空所在的位置上的值必须是0，这样子可以保证状态一样的时候int的值一定是一样的。
我们可以写下这样的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89 | #include <bits/stdc++.h>
using namespace std;
const int BLACK = 0;
const int WHITE = 1;
const int ops[] = {-3, -2, -1, 1, 2, 3};
struct State {
int code = 0;
int step = 0;
int empty;
int length;
explicit State(const string& str) {
length = str.length();
int index = length;
for (const auto& item: str) {
--index;
code <<= 1;
switch (item) {
case 'W': code += WHITE;
break;
case 'B': code += BLACK;
break;
default: empty = index;
break;
}
}
}
bool jump(int op) {
int toIndex = empty - op;
if (toIndex < 0 || toIndex >= length) return false;
++step;
set(empty, get(toIndex));
set(toIndex, 0);
empty = toIndex;
return true;
}
bool operator ==(const State& that) const {
return code == that.code && empty == that.empty;
}
bool operator <(const State& that) const {
return code == that.code ? empty < that.empty : code < that.code;
}
private:
inline int get(int index) const {
return (code >> index) & 1;
}
inline void set(int index, int value) {
if (value == 0) code &= ~(1 << index);
else code |= (1 << index);
}
};
map<State, bool> record;
queue<State> que;
int bfs(State& state, State& end) {
que.push(state);
record[state] = true;
while (!que.empty()) {
State& next = que.front();
que.pop();
for (const auto& item: ops) {
State preview(next);
if (!preview.jump(item)) continue;
if (preview == end) return preview.step;
if (!record[preview]) {
record[preview] = true;
que.push(preview);
}
}
}
return -1;
}
int main() {
string start, end;
cin >> start >> end;
if (start == end) return (printf("0"), 0);
State head(start);
State tail(end);
printf("%d", bfs(head, tail));
return 0;
}
|
查看PTA测试信息
语言：C++（G++）
结果：答案正确
最长耗时：40ms
最大内存：3252KB
相对于未优化版：
时间减少：30ms
内存减少：760KB
查重优化
int我们最多使用15位，则这个int的最大值为：32767。所以我们可以用数组代替map进行查重（map内部是红黑树，当然使用unordered_map）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95 | #include <bits/stdc++.h>
using namespace std;
const int BLACK = 0;
const int WHITE = 1;
const int ops[] = {-3, -2, -1, 1, 2, 3};
struct State {
int code = 0;
int step = 0;
int empty;
int length;
explicit State(const string& str) {
length = str.length();
int index = length;
for (const auto& item: str) {
--index;
code <<= 1;
switch (item) {
case 'W': code += WHITE;
break;
case 'B': code += BLACK;
break;
default: empty = index;
break;
}
}
}
bool jump(int op) {
int toIndex = empty - op;
if (toIndex < 0 || toIndex >= length) return false;
++step;
set(empty, get(toIndex));
set(toIndex, 0);
empty = toIndex;
return true;
}
inline bool operator==(const State& that) const {
return code == that.code && empty == that.empty;
}
private:
inline int get(int index) const {
return (code >> index) & 1;
}
inline void set(int index, int value) {
if (value == 0) code &= ~(1 << index);
else code |= (1 << index);
}
};
vector<State> record[33000];
queue<State> que;
bool noContain(State& dist) {
auto& vs = record[dist.code];
for (const auto &item : vs) {
if (item == dist) return false;
}
return true;
}
int bfs(State& state, State& end) {
que.push(state);
record[state.code].push_back(state);
while (!que.empty()) {
State& next = que.front();
que.pop();
for (const auto& item: ops) {
State preview(next);
if (!preview.jump(item)) continue;
if (preview == end) return preview.step;
if (noContain(preview)) {
record[preview.code].push_back(preview);
que.push(preview);
}
}
}
return -1;
}
int main() {
string start, end;
cin >> start >> end;
if (start == end) return (printf("0"), 0);
State head(start);
State tail(end);
printf("%d", bfs(head, tail));
return 0;
}
|
查看PTA测试信息
语言：C++（G++）
结果：答案正确
最长耗时：12ms
最大内存：2384KB
相对于未优化版：
时间减少：58ms
内存减少：1628KB
相对于哈希优化版：
时间减少：18ms
内存减少：868KB
创作不易，扫描下方打赏二维码支持一下吧ヾ(≧▽≦*)o
