题目传送门:biubiubiu~
三个水杯
时间限制：1000 ms | 内存限制：65535 KB
难度：4
- 描述
- 给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。
- 输入
- 第一行一个整数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- 这个题，讲道理，很经典。
- 当年大一的时候看这个题脑子简直就是爆炸，因为根本想不到用搜索写，而且我的搜索还很弱_(:з」∠)_
- 代码:
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=+;
int vis[maxn][maxn][maxn];
typedef struct node{
int cur[];
int step;
};
node s,e,p;
int v[];
bool match(node t){
return (t.cur[]==e.cur[]&&t.cur[]==e.cur[]&&t.cur[]==e.cur[]);
}
int BFS(){
s.cur[]=v[];
s.cur[]=s.cur[]=s.step=;
queue<node>q;
memset(vis,,sizeof(vis));
q.push(s);
vis[v[]][][]=;
while(!q.empty()){
p=q.front();q.pop();
if(match(p))return p.step;
for(int i=;i<;i++){
for(int j=;j<;++j){
if(i!=j){
int minn=min(v[j]-p.cur[j],p.cur[i]);
node v=p;
v.cur[j]+=minn;
v.cur[i]-=minn;
v.step=p.step+;
if(vis[v.cur[]][v.cur[]][v.cur[]]==){
q.push(v);
vis[v.cur[]][v.cur[]][v.cur[]]=;
}
}
}
}
}
return -;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&v[],&v[],&v[]);
scanf("%d%d%d",&e.cur[],&e.cur[],&e.cur[]);
int ans=BFS();
printf("%d\n",ans);
}
return ;
}