例7-3 倒水问题。
有装满水的6升的杯子、空的3升杯子和1升杯子，3个杯子中都没有刻度。在不使用其他道具的情况下，是否可以量出4升的水呢？
方法如图7-7所示。
图7-7 倒水问题：一种方法是(6,0,0)→(3,3,0)→(3,2,1)→(4,2,0)
注意：由于没有刻度，用杯子x给杯子y倒水时必须一直持续到把杯子y倒满或者把杯子x倒空，而不能中途停止。
你的任务是解决一般性的问题：设大、中、小3个杯子的容量分别为a,b,c，最初只有大杯子装满水，其他两个杯子为空。最少需要多少步才能让某一个杯子中的水有x升呢？你
需要打印出每步操作后各个杯子中的水量（0<c<b<a<1000）。
学习点：
有时候用数组队列保存路径时更方便，记录前驱的数组编号即可。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 105 int cap[3], x; int vis[MAXN][MAXN]; struct Node { int v[3]; int fa, dist, last_op; }; Node q[MAXN*MAXN]; void print_path(int idx) { if(q[idx].fa != idx) print_path(q[idx].fa); printf("%d %d %d\n", q[idx].v[0], q[idx].v[1], q[idx].v[2]); } void bfs() { int front=0, rear=1, i, j, k; q[0].v[0] = cap[0]; q[0].v[1] = q[0].v[2] = q[0].dist = q[0].fa = 0; vis[0][0] = 1; while(front<rear) { Node& u = q[front]; if(u.v[0] == x || u.v[1] == x || u.v[2] == x) { printf("%d\n", u.dist); print_path(front); return; } for(i = 0; i < 3; i++) for(j = 0; j < 3; j++) if(i!=j) { Node& v = q[rear]; int amount = min(u.v[i], (cap[j]-u.v[j])); for(k = 0; k < 3; k++) v.v[k] = u.v[k]; v.v[i] -= amount; v.v[j] += amount; if(!vis[v.v[1]][v.v[2]]) { //printf("%d %d %d\n", v.v[0], v.v[1], v.v[2]); vis[v.v[1]][v.v[2]] = 1; v.fa = front; v.dist = q[front].dist+1; v.last_op = i*10+j; rear++; } } front++; } } int main() { int i, j; scanf("%d%d%d%d", &cap[0], &cap[1], &cap[2], &x); memset(vis, 0, sizeof(vis)); bfs(); return 0; }
原文：http://www.cnblogs.com/cute/p/3679138.html