洛谷P1432 - 倒水问题

 题解 / 洛谷
被浏览

很容易看出这是宽度优先搜索,因为要求步数最少,且每个操作代价相同。

我们可以按操作类别分 6 种情况扩展,如果搜到最终状态就跳出 BFS(搜索顺序可以随意,因为 spj 已经配置好了,不像数据修改前要有特定的顺序)。

记得标记已经出现过的情况,不然会 TLE/MLE;

做宽搜题,队列能开多大就开多大。

正确开队列的方法:我们发现$C_{a},C_{b}$最大只有$10^3$,也就是说总状态数最多只有$10^6$,所以把队列大小开成比状态数稍微多一点就行了。

代码如下:

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
#include <bits/stdc++.h>
using namespace std;
bool vis[2005][2005];
int va, vb, vc;
void init() {
memset(vis, 0, sizeof(vis));
scanf("%d%d%d", &va, &vb, &vc);
}
struct Data {
int a, b, nxt, k, step;
} q[5000005];
void print(int p) {
int t = q[p].nxt;
if (!t) return;
print(t);
printf("%d ", q[p].k);
}
bool nxt(int l, int &r, int a, int b, int opt) { // 获取下一个状态
if (vis[a][b]) return 0; // 剪枝
r++;
q[r].a = a, q[r].b = b, q[r].k = opt;
q[r].nxt = l;
vis[a][b] = 1;
q[r].step = q[l].step + 1;
if (q[r].b == vc) {
printf("%d ", q[r].step);
print(r), puts("");
}
return q[r].b == vc;
}
void solve() {
q[1].a = q[1].b = q[1].k = q[1].nxt = q[1].step = 0;
vis[0][0] = 1;
// 初始状态
int l = 0, r = 1;
bool f = 0;
while (l < r && !f) {
l++;
f |= nxt(l, r, va, q[l].b, 1); // 把A装满
f |= nxt(l, r, q[l].a, vb, 2); // 把B装满
f |= nxt(l, r, 0, q[l].b, 3); // 把A倒空
f |= nxt(l, r, q[l].a, 0, 4); // 把B倒空
int ta = q[l].a + q[l].b, tb = 0;
if (ta > va) {
tb = ta - va;
ta = va;
} // 如果超出容量了,那么处理一下
f |= nxt(l, r, ta, tb, 5); // 把B倒给A
ta = 0, tb = q[l].a + q[l].b;
if (tb > vb) {
ta = tb - vb;
tb = vb;
}
f |= nxt(l, r, ta, tb, 6); // 把A倒给B
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
init();
solve();
}
}