题目传送门:

三个水杯

时间限制：

1000 ms  |  内存限制：65535 KB

难度：

4

 

描述

给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。

 

输入

第一行一个整数N(0<N<50)表示N组测试数据

接下来每组测试数据有两行，第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三个水杯的体积。

第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态

输出

每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1

样例输入

26 3 14 1 19 3 27 1 1

样例输出

3-1

这个题，讲道理，很经典。 当年大一的时候看这个题脑子简直就是爆炸，因为根本想不到用搜索写，而且我的搜索还很弱_(:з」∠)_  代码:

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 const int maxn=100+10; 8 int vis[maxn][maxn][maxn]; 9 typedef struct node{10     int cur[3];11     int step;12 };13 node s,e,p;14 int v[3];15 bool match(node t){16     return (t.cur[0]==e.cur[0]&&t.cur[1]==e.cur[1]&&t.cur[2]==e.cur[2]);17 }18 int BFS(){19     s.cur[0]=v[0];20     s.cur[1]=s.cur[2]=s.step=0;21     queue
          
           q;22 memset(vis,0,sizeof(vis));23 q.push(s);24 vis[v[1]][0][0]=1;25 while(!q.empty()){26 p=q.front();q.pop();27 if(match(p))return p.step;28 for(int i=0;i<3;i++){29 for(int j=0;j<3;++j){30 if(i!=j){31 int minn=min(v[j]-p.cur[j],p.cur[i]);32 node v=p;33 v.cur[j]+=minn;34 v.cur[i]-=minn;35 v.step=p.step+1;36 if(vis[v.cur[0]][v.cur[1]][v.cur[2]]==0){37 q.push(v);38 vis[v.cur[0]][v.cur[1]][v.cur[2]]=1;39 }40 }41 }42 }43 }44 return -1;45 }46 int main(){47 int t;48 scanf("%d",&t);49 while(t--){50 scanf("%d%d%d",&v[0],&v[1],&v[2]);51 scanf("%d%d%d",&e.cur[0],&e.cur[1],&e.cur[2]);52 int ans=BFS();53 printf("%d\n",ans);54 }55 return 0;56 }