题目链接：https://vjudge.net/problem/POJ-3414
题意：给你两个杯子，分别容量为A(1)，B(2)和一个C，C是需要经过下列操作，得到的一个升数。
（1） FILL(i) ：把编号为i的杯子中水灌满
（2）DROP（i）：把编号为i的杯子中水全部倒了
（3）POUR（i,j）：把编号为i的杯子中的水倒入编号为j的杯子中，如果编号j杯子中水满了，编号i杯子水就不继续倒了
问：能不能经过有限次（1）（2）（3）操作，得到A,B中其中一个满足C升的水就可以，可以的话输出最少次数并把操作输出，否则输出“impossble”
思路：最少，容易想到bfs，加上倒水过程的模拟，也就6种情况，模拟操作预处理之后，后面会变得很好写，其中的过程，看代码注释吧。
补：我们可以把A，B中升数情况给记录下，出现过的<A,B>就不需要再次bfs了，不然应该会TLE
1 #include <iostream> 2 #include <cstring> 3 #include<vector> 4 #include<string> 5 #include <cmath> 6 #include <map> 7 #include <queue> 8 #include <algorithm> 9 using namespace std; 10 11 #define inf (1LL << 31) - 1 12 #define rep(i,j,k) for(int i = (j); i <= (k); i++) 13 #define rep__(i,j,k) for(int i = (j); i < (k); i++) 14 #define per(i,j,k) for(int i = (j); i >= (k); i--) 15 #define per__(i,j,k) for(int i = (j); i > (k); i--) 16 17 int A_L, B_L, C_L; 18 19 //六种操作，都先预处理好 20 string op[6] = { "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", 21 "POUR(1,2)", "POUR(2,1)" }; 22 //其实算一个类用 23 struct node{ 24 25 int A,B; //A，B杯子中水升数情况 26 vector<string > str; //记录操作 27 // int l; 28 node(int a = 0, int b = 0){ A = a; B = b; } 29 30 void Fill(int num){ //（1）操作处理 31 if (num == 1) A = A_L; 32 else B = B_L; 33 } 34 35 void Drop(int num){ //（2）操作处理 36 if (num == 1) A = 0; 37 else B = 0; 38 } 39 40 void Pour(int num){ //（3）操作处理 41 if (num == 1){ 42 int tmp = A; 43 A -= (A >= B_L - B ? (B_L - B) : A); 44 B = (tmp >= B_L - B ? B_L : B + tmp); 45 } 46 else{ 47 int tmp = B; 48 B -= (B >= A_L - A ? (A_L - A) : B); 49 A = (tmp >= A_L - A ? A_L : A + tmp); 50 } 51 } 52 53 }; 54 55 void fun(string str){ 56 cout << str << endl; 57 } 58 59 void bfs(){ 60 61 map<pair<int, int>, bool> mp; //记录<A,B>的情况 62 63 node init; 64 /* 65 pair<int,int > p (init.A, init.B); 66 mp[p] = true; 67 */ 68 69 queue<node> que; 70 que.push(init); 71 72 while (!que.empty()){ 73 74 node key = que.front(); 75 que.pop(); 76 77 pair<int, int> o( key.A, key.B ); 78 if (mp[o]) continue; //判断这个<A,B>有误出现过，出现了就不继续下去了 79 mp[o] = true; //没出现过，标记一下 80 81 //六种情况 82 rep(p, 1, 6){ 83 84 node tmp = key; 85 86 if (p == 1) tmp.Fill(1),tmp.str.push_back(op[0]); 87 else if (p == 2) tmp.Fill(2), tmp.str.push_back(op[1]); 88 else if (p == 3) tmp.Drop(1), tmp.str.push_back(op[2]); 89 else if (p == 4) tmp.Drop(2), tmp.str.push_back(op[3]); 90 else if (p == 5) tmp.Pour(1), tmp.str.push_back(op[4]); //pour(1,2) 91 else if (p == 6) tmp.Pour(2), tmp.str.push_back(op[5]); //pour(2,1) 92 93 //其中一个满足即可 94 if (tmp.A == C_L || tmp.B == C_L){ 95 cout << (int)tmp.str.size() << endl; 96 97 //遍历tmp的vector 98 for_each(tmp.str.begin(), tmp.str.end(), fun); 99 100 return; 101 } 102 103 o = make_pair(tmp.A, tmp.B); //也是判断下新的<A,B>是否出现过 104 if (!mp[o]) que.push(tmp); //出现过，不再压入队列 105 } 106 } 107 108 //无法得出C 109 cout << "impossible" << endl; 110 111 } 112 113 int main(){ 114 115 ios::sync_with_stdio(false); 116 cin.tie(0); 117 118 cin >> A_L >> B_L >> C_L; //记录A的最大容量，B的最大容量，标准C 119 bfs(); 120 121 return 0; 122 }