三个水杯

描述

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

 

输入

第一行一个整数N(0<N<50)表示N组测试数据
接下来每组测试数据有两行，第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三个水杯的体积。
第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态

输出

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

样例输入

2

6 3 1

4 1 1

9 3 2

7 1 1

样例输出

3

-1

题解：bfs里用两个循环代表从j往i杯子里倒水；

代码：

 #include<stdio.h>

 #include<string.h>

 #include<queue>

 using namespace std;

 struct Node{

     int wat[];

     int step;

 };

 int cup[];

 int res[];

 int vis[][];

 void bfs(int sx,int sy,int sz){

     memset(vis,,sizeof(vis));

     queue<Node>dl;

     Node a,b;

     a.wat[]=sx;a.wat[]=sy;a.wat[]=sz;

     vis[sx][sy]=;

     a.step=;

     dl.push(a);

     while(!dl.empty()){

         a=dl.front();

         dl.pop();

         if(a.wat[]==res[]&&a.wat[]==res[]&&a.wat[]==res[]){

                         printf("%d\n",a.step);

                         return;

                     }

         for(int i=;i<;i++)

             for(int j=;j<;j++){

                 b=a;

                 b.step++;

                 if(i!=j){

                     //printf("%d %d %d\n",b.wat[0],b.wat[1],b.wat[2]);

                     if(a.wat[j]+a.wat[i]<=cup[i]){

                         b.wat[i]=a.wat[i]+a.wat[j];

                         b.wat[j]=;

                     }

                     else{

                         b.wat[i]=cup[i];

                         b.wat[j]=a.wat[j]-(cup[i]-a.wat[i]);

                     }

                     if(b.wat[]==res[]&&b.wat[]==res[]&&b.wat[]==res[]){

                         printf("%d\n",b.step);

                         return;

                     }

                     //printf("%d %d %d %d\n",b.wat[0],b.wat[1],b.wat[2],b.step);

                     if(!vis[b.wat[]][b.wat[]])dl.push(b);

                     vis[b.wat[]][b.wat[]]=;

                 }

             }

     }

     puts("-1");

 }

 int main(){

     int N;

     scanf("%d",&N);

     while(N--){

         for(int i=;i<;i++)scanf("%d",cup+i);

         for(int i=;i<;i++)scanf("%d",res+i);

         bfs(cup[],,);

     }

     return ;

 }

bfs优化：

 #include<stdio.h>

 #include<string.h>

 #include<queue>

 using namespace std;

 struct Node{

     int wat[];

     int step;

     friend bool operator < (Node a,Node b){

         return a.step>b.step;

     }

 };

 int cup[];

 int res[];

 int vis[][];

 void bfs(int sx,int sy,int sz){

     memset(vis,,sizeof(vis));

     priority_queue<Node>dl;

     Node a,b;

     a.wat[]=sx;a.wat[]=sy;a.wat[]=sz;

     vis[sx][sy]=;

     a.step=;

     dl.push(a);

     while(!dl.empty()){

         a=dl.top();

         dl.pop();

         if(a.wat[]==res[]&&a.wat[]==res[]&&a.wat[]==res[]){

                         printf("%d\n",a.step);

                         return;

                     }

         for(int i=;i<;i++)

             for(int j=;j<;j++){

                 b=a;

                 b.step++;

                 if(i!=j){

                     //printf("%d %d %d\n",b.wat[0],b.wat[1],b.wat[2]);

                     if(a.wat[j]+a.wat[i]<=cup[i]){

                         b.wat[i]=a.wat[i]+a.wat[j];

                         b.wat[j]=;

                     }

                     else{

                         b.wat[i]=cup[i];

                         b.wat[j]=a.wat[j]-(cup[i]-a.wat[i]);

                     }

                     if(b.wat[]==res[]&&b.wat[]==res[]&&b.wat[]==res[]){

                         printf("%d\n",b.step);

                         return;

                     }

                     //printf("%d %d %d %d\n",b.wat[0],b.wat[1],b.wat[2],b.step);

                     if(!vis[b.wat[]][b.wat[]])dl.push(b);

                     vis[b.wat[]][b.wat[]]=;

                 }

             }

     }

     puts("-1");

 }

 int main(){

     int N;

     scanf("%d",&N);

     while(N--){

         for(int i=;i<;i++)scanf("%d",cup+i);

         for(int i=;i<;i++)scanf("%d",res+i);

         bfs(cup[],,);

     }

     return ;

 }