描述
给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。
-
输入
-
第一行一个整数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
思路：题目给出三个杯子的体积V1,V2,V3, 并且给出了最后要倒成的水杯中的水数量的状态。
假设，当前水杯中的水量是(cur1,cur2,cur3)。那么每一个状态为一个结点的话，那么倒水的方式即为结点之间的连线。从一个结点(状态)到另一个结点(状态)的最短路(最少 的次数)。用宽度优先遍历的方式，对结点进行搜索，即可获得最少次数。
1、结点可以定义一个结构体来表示。
2、状态转移的方式枚举倒法，一共是3*3-3种,因为不能自己给自己的杯子中倒水。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 105
using namespace std;
int x1,y1,z1;
int x2,y2,z2;
int ans,t,flag;
struct Cup{int v[3];//杯子的容积 int cur[3];//当前杯子里面的水的体积 int steps;
};
bool match(Cup s){return (s.cur[0]==x2&&s.cur[1]==y2&&s.cur[2]==z2);}int vis[N][N][N];
queue<Cup> q;
Cup u1;
void bfs(){q.push(u1);while(!q.empty()){Cup u2=q.front();if(match(u2)){ans = u2.steps;flag = 1;return ;}//从i杯子倒入j杯子 for(int i=0 ;i<3 ;i++){for(int j=0 ;j<3 ;j++){if(i!=j){Cup u3 = u2;int min = u3.v[j]-u3.cur[j];// j杯子的容积-j杯子中当前水体积(还能倒如多少水) if(min>u3.cur[i]){//判断i杯子中是否有足够的水倒入j min = u3.cur[i];}//倒水u3.cur[i] -= min;u3.cur[j] += min; u3.steps+=1;if(!vis[u3.cur[0]][u3.cur[1]][u3.cur[2]]){q.push(u3);vis[u3.cur[0]][u3.cur[1]][u3.cur[2]]=1;}}}}q.pop();}}int main(){scanf("%d",&t);while(t--){scanf("%d%d%d",&x1,&y1,&z1);scanf("%d%d%d",&x2,&y2,&z2);memset(vis,0,sizeof(vis));flag = 0;u1.v[0] =x1; u1.v[1] =y1; u1.v[2] =z1; u1.cur[0] =x1; u1.cur[1] =0; u1.cur[2] =0;vis[x1][0][0] = 1;bfs();if(flag)printf("%d\n",ans);elseputs("-1");}return 0;
}