题目：
泊松是法国数学家、物理学家和力学家。他一生致力科学事业，成果颇多。有许多著名的公式定理以他的名字命名，比如概率论中著名的泊松分布。
有一次闲暇时，他提出过一个有趣的问题，后称为：“泊松分酒”。在我国古代也提出过类似问题，遗憾的是没有进行彻底探索，其中流传较多是：“韩信走马分油”问题。
有3个容器，容量分别为12升，8升，5升。其中12升中装满油，另外两个空着。要求你只用3个容器操作，最后使得某个容器中正好有6升油。
下面的列表是可能的操作状态记录：
12,0,0
4,8,0
4,3,5
9,3,0
9,0,3
1,8,3
1,6,5
每行3个数据，分别表示12，8，6升容器中的油量
第一行表示初始状态，第二行表示把12升倒入8升容器后的状态，第三行是8升倒入5升，...
当然，同一个题目可能有多种不同的正确操作步骤。
本题目的要求是，请你编写程序，由用户输入：各个容器的容量，开始的状态，和要求的目标油量，程序则通过计算输出一种实现的步骤（不需要找到所有可能的方法）。如果没有可能实现，则输出：“不可能”。
例如，用户输入：
12,8,5,12,0,0,6
用户输入的前三个数是容器容量（由大到小），接下来三个数是三个容器开始时的油量配置，最后一个数是要求得到的油量（放在哪个容器里得到都可以）
则程序可以输出（答案不唯一，只验证操作可行性）：
12,0,0
4,8,0
4,3,5
9,3,0
9,0,3
1,8,3
1,6,5
每一行表示一个操作过程中的油量状态。
题目理解：
利用BFS的方法可以搜索出是否能够完成，然后利用有前驱的链表进行记录。
代码：
/*
ID:泊松分酒
LANG:C++
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#include <algorithm>
#define SWAP(x,y) {(x) = (x)^(y); (y)=(x)^(y); (x)=(x)^(y);}
#define MIN(x,y) (x<y?x:y)
#define INF 1e9
#define MAXN 100
struct Node{
int a,b,c;
struct Node *pre;
}node[MAXN*MAXN*MAXN],init; //init记录容器的最大容量
bool visit[MAXN][MAXN][MAXN];
void print(struct Node now){ //递归输出
if(now.pre != NULL){
print(*now.pre);
}
printf("%d,%d,%d\n", now.a, now.b, now.c);
}
void bfs(int target){
int head = 0, tail = 1;
node[0].pre = NULL;
visit[node[0].a][node[0].b][node[0].c] = true;
while(tail-head>0){
int count = tail-head;
while(count--){
struct Node now = node[head];
if(now.a==target||now.b==target||now.c==target){
print(now);
return;
}
int min = MIN(now.a, init.b-now.b); //a向b中倒
if(!visit[now.a-min][now.b+min][now.c]){
node[tail].a = now.a-min;
node[tail].b = now.b+min;
node[tail].c = now.c;
node[tail].pre = &node[head];
visit[now.a-min][now.b+min][now.c] = true;
tail++;
}
min = MIN(now.a, init.c-now.c); //a向c中倒
if(!visit[now.a-min][now.b][now.c+min]){
node[tail].a = now.a-min;
node[tail].b = now.b;
node[tail].c = now.c+min;
node[tail].pre = &node[head];
visit[now.a-min][now.b][now.c+min] = true;
tail++;
}
min = MIN(init.a-now.a, now.b); //b向a
if(!visit[now.a+min][now.b-min][now.c]){
node[tail].a = now.a+min;
node[tail].b = now.b-min;
node[tail].c = now.c;
node[tail].pre = &node[head];
visit[now.a+min][now.b-min][now.c] = true;
tail++;
}
min = MIN(now.b, init.c-now.c); //b向c
if(!visit[now.a][now.b-min][now.c+min]){
node[tail].a = now.a;
node[tail].b = now.b-min;
node[tail].c = now.c+min;
node[tail].pre = &node[head];
visit[now.a][now.b-min][now.c+min] = true;
tail++;
}
min = MIN(init.a-now.a, now.c); //c向a
if(!visit[now.a+min][now.b][now.c-min]){
node[tail].a = now.a+min;
node[tail].b = now.b;
node[tail].c = now.c-min;
node[tail].pre = &node[head];
visit[now.a+min][now.b][now.c-min] = true;
tail++;
}
min = MIN(init.b-now.b, now.c); //c向b
if(!visit[now.a][now.b+min][now.c-min]){
node[tail].a = now.a;
node[tail].b = now.b+min;
node[tail].c = now.c-min;
visit[now.a][now.b+min][now.c-min] = true;
tail++;
}
head++;
}
}
printf("Impossible\n");
}
int main(){
memset(visit, false, sizeof(visit));
int target;
scanf("%d,%d,%d,%d,%d,%d,%d",
&init.a, &init.b,&init.c,&node[0].a,&node[0].b,&node[0].c,&target);
bfs(target);
return 0;
}
参考样例：
/* 样例1： 输入： 12,8,5,12,0,0,6 输出： 12,0,0 4,8,0 4,3,5 9,3,0 9,0,3 1,8,3 1,6,5 样例2： 输入： 30,13,7,30,0,0,5 输出： 30,0,0 17,13,0 17,6,7 24,6,0 24,0,6 11,13,6 11,12,7 18,12,0 18,5,7 样例3： 输入： 31,19,11,31,0,0,5 输出： 31,0,0 12,19,0 12,8,11 23,8,0 23,0,8 4,19,8 4,16,11 15,16,0 15,5,11 样例4： 输入： 65,33,12,65,0,0,18 输出： 65,0,0 32,33,0 32,21,12 44,21,0 44,9,12 56,9,0 56,0,9 23,33,9 23,30,12 35,30,0 35,18,12 */
附言：
由于没有使用STL，所以代码比较冗长。如果能很好的使用STL，可以很大程度的简约代码。
原文：http://blog.csdn.net/mullerwch/article/details/21028393