UVa 571. Jugs
Description
在電影「終極警探 3（Die Hard 3）」中布魯斯威利（Bruce Willis）和山謬傑克森（Samuel L. Jackson）遇到壞蛋設下的謎題：給一個3加侖和5加侖的桶子，要求他們必須在5加侖的桶子中裝4加侖的水。現在你的任務就是解決這個問題。
給你2個桶子A、B和無限供應的水，你可以做3個動作：
- 把一個桶子裝滿水。
- 把一個桶子的水倒光。
- 把一個桶子的水倒到另一個桶子中。
把水從一個桶子倒到另一個桶子的動作停止有2個可能的原因：第一個桶子的水倒光了或第二個桶子的水滿了。例如：A有5加侖的水，B有6加侖的水且B的容量為8加侖，則當把A的水倒到B後，B就滿了（8加侖）而A中還剩3加侖。在本問題中，給你Ca,Cb,N。Ca,Cb分別代表A桶子和B桶子的容量而N是我們要求的目標。我們希望你的程式輸出一連串的動作之後，可以得到N加侖的水（不論在A或B中都可以）。這一連串的動作包含：
- fill A
- fill B
- empty A
- empty B
- pour A B
- pour B A
- success
在這裡，“pour A B"代表把A的水倒到B中，而"success"代表任務已經完成了。你可以假設給你的輸入一定有解答。
Input Format
每組測試資料一列，含有3個正整數Ca,Cb,N。（ $0 < \textrm{Ca} \le \textrm{Cb}，\textrm{N} \le \textrm{Cb} \le 1000$ ）
Output Format
每組測試資料輸出一連串的動作（總是以success作為結束），使得可以得到N加侖的水（不論在A或B中都可以）。請參考Sample Output。
Sample Input
3 5 4
5 7 3
1 1 1
Sample Output
fill B
pour B A
empty A
pour B A
fill B
pour B A
success
fill A
pour A B
fill A
pour A B
success
fill A
success
Solution
這題可以利用BFS來做，每次都模擬6種操作，直到達成目標為止。
本題利用STL容器的Queue來模擬BFS。
Code
/*************************************************************************
> File Name: 571 - Jugs.cpp
> Author: Samuel
> Mail: enminghuang21119@gmail.com
> Created Time: Mon Jan 22 20:09:12 2018
*************************************************************************/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct node {
int A, B;
vector<int> moves;
};
bool state[1005][1005];
/*
* 0 -> A fill
* 1 -> B fill
* 2 -> A -> B
* 3 -> B -> A
* 4 -> A empty
* 5 -> B empty
*/
void out(int in) {
switch (in) {
case 0:
cout << "fill A" << '\n'; break;
case 1:
cout << "fill B" << '\n'; break;
case 2:
cout << "pour A B" << '\n'; break;
case 3:
cout << "pour B A" << '\n'; break;
case 4:
cout << "empty A" << '\n'; break;
case 5:
cout << "empty B" << '\n'; break;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int a, b, n;
while (cin >> a >> b >> n) {
node now, tmp;
queue<node> que;
now.A = now.B = 0;
que.push(now);
for (int i = 0; i < 1005; i++) for (int j = 0; j < 1005; j++) state[i][j] = 1;
while (!que.empty()) {
now = que.front();
que.pop();
if (now.B == n)
break;
for (int i = 0; i < 6; i++) {
tmp = now;
tmp.moves.push_back(i);
switch (i) {
case 0:
if (now.A < a) {
tmp.A = a;
que.push(tmp);
if (state[tmp.A][tmp.B]) {
que.push(tmp);
state[tmp.A][tmp.B] = 0;
}
}
break;
case 1:
if (now.B < b) {
tmp.B = b;
if (state[tmp.A][tmp.B]) {
que.push(tmp);
state[tmp.A][tmp.B] = 0;
}
}
break;
case 2:
if (now.B < b && now.A > 0) {
tmp.B += tmp.A;
tmp.A = 0;
if (tmp.B > b)
tmp.A = tmp.B - b, tmp.B = b;
if (state[tmp.A][tmp.B]) {
que.push(tmp);
state[tmp.A][tmp.B] = 0;
}
}
break;
case 3:
if (now.A < a && now.B > 0) {
tmp.A += tmp.B;
tmp.B = 0;
if (tmp.A > a)
tmp.B = tmp.A - a, tmp.A = a;
if (state[tmp.A][tmp.B]) {
que.push(tmp);
state[tmp.A][tmp.B] = 0;
}
}
break;
case 4:
if (now.A > 0) {
tmp.A = 0;
if (state[tmp.A][tmp.B]) {
que.push(tmp);
state[tmp.A][tmp.B] = 0;
}
}
break;
case 5:
if (now.B > 0) {
tmp.B = 0;
if (state[tmp.A][tmp.B]) {
que.push(tmp);
state[tmp.A][tmp.B] = 0;
}
}
break;
}
}
}
int size = now.moves.size();
for (int i = 0; i < size; i++)
out(now.moves[i]);
cout << "success\n";
}
return 0;
}