Description
有三个无刻度标志的水杯，分别可装 a ，b , c升水，并且a>b , a>c , a,b,c,均为正整数。任意两个水杯之间可以相互倒水。用
杯子x给y倒水的时必须一直持续到把杯子y倒满或者把杯子x倒空，而不能中途停止。倒水过程中水量不变。最初的时候只有大杯子
装满水，其他两个杯子为空。问能不能量出x升水，如果可以，最少需要多少步？
Input
输入有多组数据。每组数据为一行,有4个正整数a，b，c，x且满足：a>b，a>c，a>x，a，b，c，x <= 1000。
Output
输出一个整数。如果可以量出x升水，输出需要的最少步骤，否则，输出-1。
Sample Input
6 3 1 4
7 3 2 5
Sample Output
3
1
将每个杯子中的水量组合成状态，进行宽搜即可。
View Code
#include <stdio.h> #include <queue> #define N 1001 #define MIN(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef struct node { int a[3]; }node; int v[3],x; int t[N][N]; bool isok(node tmp) { for(int i=0;i<3;i++) if(tmp.a[i]==x) return true; return false; } node tran(node tmp,int i,int j) { int d=MIN(tmp.a[i],v[j]-tmp.a[j]); tmp.a[i]-=d; tmp.a[j]+=d; return tmp; } void bfs() { queue<node> q; node cur,next; bool success=false; int i,j,ans; for(i=0;i<=v[0];i++) { for(j=0;j<=v[0];j++) t[i][j]=-1; } cur.a[0]=v[0]; cur.a[1]=0; cur.a[2]=0; t[v[0]][0]=0; q.push(cur); while(!q.empty() && !success) { cur=q.front(),q.pop(); if(isok(cur)) { success=true; ans=t[cur.a[0]][cur.a[1]]; } for(i=0;i<3 && !success;i++) { for(j=0;j<3 && !success;j++) { if(i==j) continue; if(cur.a[i]==0 || cur.a[j]==v[j]) continue; next=tran(cur,i,j); if(t[next.a[0]][next.a[1]]!=-1) continue; t[next.a[0]][next.a[1]]=t[cur.a[0]][cur.a[1]]+1; if(isok(next)) { success=true; ans=t[next.a[0]][next.a[1]]; } else q.push(next); } } } if(success) printf("%d\n",ans); else puts("-1"); } int main() { while(~scanf("%d%d%d%d",&v[0],&v[1],&v[2],&x)) bfs(); return 0; }