洛谷P1432 - 倒水问题

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

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

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

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

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

代码如下：

#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();
    }
}