三个水杯
时间限制： 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
题解：bfs里用两个循环代表从j往i杯子里倒水； - 代码：
-
1 #include
2 #include 3 #include 4 using namespace std; 5 struct Node{ 6 int wat[3]; 7 int step; 8 }; 9 int cup[3];10 int res[3];11 int vis[110][110];12 void bfs(int sx,int sy,int sz){13 memset(vis,0,sizeof(vis));14 queue dl;15 Node a,b;16 a.wat[0]=sx;a.wat[1]=sy;a.wat[2]=sz;17 vis[sx][sy]=1;18 a.step=0;19 dl.push(a);20 while(!dl.empty()){21 a=dl.front();22 dl.pop();23 if(a.wat[0]==res[0]&&a.wat[1]==res[1]&&a.wat[2]==res[2]){24 printf("%d\n",a.step);25 return;26 }27 for(int i=0;i<3;i++)28 for(int j=0;j<3;j++){29 b=a;30 b.step++;31 if(i!=j){32 //printf("%d %d %d\n",b.wat[0],b.wat[1],b.wat[2]);33 if(a.wat[j]+a.wat[i]<=cup[i]){34 b.wat[i]=a.wat[i]+a.wat[j];35 b.wat[j]=0;36 }37 else{38 b.wat[i]=cup[i];39 b.wat[j]=a.wat[j]-(cup[i]-a.wat[i]);40 }41 if(b.wat[0]==res[0]&&b.wat[1]==res[1]&&b.wat[2]==res[2]){42 printf("%d\n",b.step);43 return;44 }45 //printf("%d %d %d %d\n",b.wat[0],b.wat[1],b.wat[2],b.step);46 if(!vis[b.wat[0]][b.wat[1]])dl.push(b);47 vis[b.wat[0]][b.wat[1]]=1;48 }49 }50 }51 puts("-1");52 }53 int main(){54 int N;55 scanf("%d",&N);56 while(N--){57 for(int i=0;i<3;i++)scanf("%d",cup+i);58 for(int i=0;i<3;i++)scanf("%d",res+i);59 bfs(cup[0],0,0);60 }61 return 0;62 } bfs优化：
1 #include
2 #include 3 #include 4 using namespace std; 5 struct Node{ 6 int wat[3]; 7 int step; 8 friend bool operator < (Node a,Node b){ 9 return a.step>b.step;10 }11 };12 int cup[3];13 int res[3];14 int vis[110][110];15 void bfs(int sx,int sy,int sz){16 memset(vis,0,sizeof(vis));17 priority_queue dl;18 Node a,b;19 a.wat[0]=sx;a.wat[1]=sy;a.wat[2]=sz;20 vis[sx][sy]=1;21 a.step=0;22 dl.push(a);23 while(!dl.empty()){24 a=dl.top();25 dl.pop();26 if(a.wat[0]==res[0]&&a.wat[1]==res[1]&&a.wat[2]==res[2]){27 printf("%d\n",a.step);28 return;29 }30 for(int i=0;i<3;i++)31 for(int j=0;j<3;j++){32 b=a;33 b.step++;34 if(i!=j){35 //printf("%d %d %d\n",b.wat[0],b.wat[1],b.wat[2]);36 if(a.wat[j]+a.wat[i]<=cup[i]){37 b.wat[i]=a.wat[i]+a.wat[j];38 b.wat[j]=0;39 }40 else{41 b.wat[i]=cup[i];42 b.wat[j]=a.wat[j]-(cup[i]-a.wat[i]);43 }44 if(b.wat[0]==res[0]&&b.wat[1]==res[1]&&b.wat[2]==res[2]){45 printf("%d\n",b.step);46 return;47 }48 //printf("%d %d %d %d\n",b.wat[0],b.wat[1],b.wat[2],b.step);49 if(!vis[b.wat[0]][b.wat[1]])dl.push(b);50 vis[b.wat[0]][b.wat[1]]=1;51 }52 }53 }54 puts("-1");55 }56 int main(){57 int N;58 scanf("%d",&N);59 while(N--){60 for(int i=0;i<3;i++)scanf("%d",cup+i);61 for(int i=0;i<3;i++)scanf("%d",res+i);62 bfs(cup[0],0,0);63 }64 return 0;65 }