题目链接：https://vjudge.net/problem/HDU-1495
题意：有两个空杯（分别是N升和M升）和一罐满的可乐S升，S = N + M,三个容器可以互相倾倒，如果A倒入B，只有两种情况：
（1） A全部倒入B中，B中的升数小于等于B的最大容量。
（2）A部分倒入B中，B已经到达了B的最大容量。
问：有没有可能把S升的可乐平分在任意两个容器中，有的话得出最少操作次数，否则输出“NO”。
思路：bfs，把六种情况都模拟枚举（代码写的比较形象），需要标记出现过的三个容器的容量情况，否则会TLE。
#include <iostream>
#include <cstring>
#include<vector>
#include<string>
#include <cmath>
#include <map>
#include <queue>
#include <algorithm>
using namespace std; #define inf (1LL << 31) - 1
#define rep(i,j,k) for(int i = (j); i <= (k); i++)
#define rep__(i,j,k) for(int i = (j); i < (k); i++)
#define per(i,j,k) for(int i = (j); i >= (k); i--)
#define per__(i,j,k) for(int i = (j); i > (k); i--) int NL, ML, SL, AVE;
//bool vis[110][110][110]; struct node{ int N, M, S, V; node(int a, int b, int c, int d){
N = a;
M = b;
S = c;
V = d;
} //这里面内嵌的 if表示（1）情况
// else表示（2）情况
void Pour(int f, int s){ if (f == ){
if (s == ){
int t = ML - M;
if (N >= t) N -= t, M = ML; //（1）
else M += N, N = ; //（2）
}
else if (s == ){
int t = SL - S;
if (N >= t) N -= t, S = SL;
else S += N, N = ;
}
}
else if (f == ){
if (s == ){
int t = NL - N;
if (M >= t) M -= t, N = NL;
else N += M, M = ;
}
else if (s == ){
int t = SL - S;
if (M >= t) M -= t, S = SL;
else S += M, M = ;
}
}
else if (f == ){
if (s == ){
int t = NL - N;
if (S >= t) S -= t, N = NL;
else N += S, M = ;
}
else if (s == ){
int t = ML - M;
if (S >= t) S -= t, M = ML;
else M += S, S = ;
}
}
} }; //可以看出，我用了两个方法都可以标记情况
void bfs(){ map<pair<int, int>, bool> mp;//标记三个容器的容量情况，防止出下过的再次出现在队列中
pair<int, int > p(, );
mp[p] = true;
node in(, , SL, );
// vis[in.N][in.M][in.S] = true;
queue<node> que;
que.push(in); while (!que.empty()){ node tmp = que.front();
que.pop(); //六种情况，Pour（x,y） 把X中的倒入y中，应该是很清楚了
rep(i, , ){
node t = tmp; if (i == ) t.Pour(, );
else if (i == ) t.Pour(, );
else if (i == ) t.Pour(, );
else if (i == ) t.Pour(, );
else if (i == ) t.Pour(, );
else if (i == ) t.Pour(, ); //检查有没有出现平分了
int key = ;
if (t.N == AVE) key++;
if (t.M == AVE) key++;
if (t.S == AVE) key++;
//平分了
if (key >= ){
cout << tmp.V + << endl;
return;
} p.first = t.N;
p.second = t.M;
pair<int, int > p(t.N, t.M);
if (!mp[p]/*!vis[t.N][t.M][t.S]*/){
mp[p] = true;
// vis[t.N][t.M][t.S] = true;
que.push(node{ t.N, t.M, t.S, tmp.V + });
}
}
} cout << "NO" << endl;
} int main(){ ios::sync_with_stdio(false);
cin.tie(); while (cin >> SL >> NL >> ML){ memset(vis, , sizeof(vis)); if (NL == && ML == && SL == ) break;
AVE = SL / ;
if (SL & ){
cout << "NO" << endl;
continue;
}
bfs();
} return ;
}