正经题解｜非常可乐

【算法分析】

分析题目可以发现，这三个杯子的状态只有 $100*100*100=10^6$ 个，可以从 $(s,0,0)$ 开始广搜，三个杯子互相倒水，直到出现有两杯一样多，且另外一杯为 $0$。

【参考代码】

#include<bits/stdc++.h>
using namespace std;

bool vis[109][109][109];
struct node {
    int a, b, c, step;
}l, r;
int main() {
    int s, n, m;
    cin >> s >> n >> m;
    queue<node> q;
    q.push({ s,0,0,0 });
    vis[s][0][0] = 1;
    while (q.size()) {
        r = q.front();
        q.pop();
        if ((r.a == 0 && r.b == r.c) || (r.b == 0 && r.a == r.c) || (r.c == 0 && r.a == r.b)) {
            cout << r.step << '\n';
            return 0;
        }
        l.a = max(0, r.a + r.b - n), l.b = min(n, r.a + r.b), l.c = r.c, l.step = r.step + 1;
        if (!vis[l.a][l.b][l.c]) {
            q.push(l);
            vis[l.a][l.b][l.c] = 1;
        }
        l.a = max(0, r.a + r.c - m), l.b = r.b, l.c = min(m, r.a + r.c), l.step = r.step + 1;
        if (!vis[l.a][l.b][l.c]) {
            q.push(l);
            vis[l.a][l.b][l.c] = 1;
        }
        l.a = min(s, r.a + r.b), l.b = max(0, r.a + r.b - s), l.c = r.c, l.step = r.step + 1;
        if (!vis[l.a][l.b][l.c]) {
            q.push(l);
            vis[l.a][l.b][l.c] = 1;
        }
        l.a = r.a, l.b = max(0, r.b + r.c - m), l.c = min(m, r.b + r.c);
        if (!vis[l.a][l.b][l.c]) {
            q.push(l);
            vis[l.a][l.b][l.c] = 1;
        }
        l.a = min(s, r.a + r.c), l.b = r.b, l.c = max(0, r.a + r.c - s);
        if (!vis[l.a][l.b][l.c]) {
            q.push(l);
            vis[l.a][l.b][l.c] = 1;
        }
        l.a = r.a, l.b = min(n, r.b + r.c), l.c = max(0, r.b + r.c - n);
        if (!vis[l.a][l.b][l.c]) {
            q.push(l);
            vis[l.a][l.b][l.c] = 1;
        }
    }
    cout << "-1" << '\n';
    return 0;
}

【时间复杂度】

$O(s*n*m)$

【预计得分】

$100pts$