三个水杯
时间限制：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 <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct Bottle {
int v[];
int step;
Bottle() {};
Bottle(int u, int v, int w, int s) {
this->v[] = u; this->v[] = v; this->v[] = w;
step = s;
}
}; queue <Bottle> bot;
int visit[][][]; bool isEqual(Bottle p, int e[]) {
for(int i = ; i < ; i++) {
if(p.v[i] != e[i]) {
return false;
}
}
return true;
}
int main(int argc, char const *argv[])
{
int N;
scanf("%d",&N);
while(N--) {
int v[];
int e[];
scanf("%d %d %d",&v[],&v[],&v[]);
scanf("%d %d %d",&e[],&e[],&e[]); while(!bot.empty()) {
bot.pop();
}
memset(visit, , sizeof(visit));
bot.push(Bottle(v[],,,)); int ans = -;
while(!bot.empty()) {
Bottle p = bot.front();
bot.pop();
if(isEqual(p,e))
{
ans = p.step;
break;
}
else {
for(int i = ; i < ; i++) {
for(int j = ; j < ; j++) {
int k = (i+j)%;
//from i to k
if(p.v[i] > && p.v[k] < v[k]) {
int cha = v[k] - p.v[k];
int pour = min(p.v[i], cha);
Bottle t;
t.v[i] = p.v[i] - pour;
t.v[k] = p.v[k] + pour;
t.v[-i-k] = p.v[-i-k];
t.step = p.step+;
if(visit[t.v[]][t.v[]][t.v[]] != ) {
visit[t.v[]][t.v[]][t.v[]] = ;
bot.push(t);
}
}
}
}
}
}
printf("%d\n", ans); }
return ;
}