21-三个水杯
内存限制:64MB
时间限制:1000ms
Special Judge: No
accepted:7
submit:18
题目描述:
给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。
输入描述:
第一行一个整数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的思想模拟，每一次（从6种倒水可能中进行抉择与判断）倒水将会参会什么样的结果 步骤：
①、初始化队列的首相，即就是最开始的水的分配情况
②、循环6步操作，考虑同样的水在6中不同情况下的分配如何，分别入队列
③、依次遍历出所有的情况，如果可以得到结果的话，就输出步骤，否则如果遍历完了都没能得到结果就return -1 核心代码：
int bfs()
{
queue<node> Q;
node q1, q2;
memset(book, , sizeof(book));
q1.temp[] = A[], q1.temp[] = , q1.temp[] = ;
book[q1.temp[]][][] = ;
Q.push(q1);
while(!Q.empty())
{
q1 = Q.front();
if(q1.temp[] == B[] && q1.temp[] == B[]
&& q1.temp[] == B[])
return q1.step;
for(int i = ; i < ; ++ i)
{
for(int j = ; j < ; ++ j)
{
if (i == j) continue; // 自己不向自己倒水
q2 = q1;
int my_change = min(q1.temp[i], A[j] - q1.temp[j]); // 将i杯中的水倒入j杯，A[j] - q1.temp[j],表明j杯最多可以得到的水量
q2.temp[i] = q1.temp[i] - my_change;
q2.temp[j] = q1.temp[j] + my_change;
q2.step = q1.step + ;
if(!book[q2.temp[]][q2.temp[]][q2.temp[]])
{
book[q2.temp[]][q2.temp[]][q2.temp[]];
Q.push(q2);
}
}
}
Q.pop();
}
return -;
}
C/C++代码实现（AC）:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <stack>
#include <map>
#include <queue> using namespace std;
const int MAXN = ;
int A[], B[], book[MAXN][MAXN][MAXN];
struct node
{
int temp[], step;
}; bool match(node q, int a, int b, int c)
{
if(q.temp[] == a && q.temp[] == b && q.temp[] == c) return true;
return false;
} int bfs()
{
node q1, q2;
q1.temp[] = A[], q1.temp[] = , q1.temp[] = , q1.step = ;
queue<node> Q;
Q.push(q1);
memset(book, , sizeof(book));
book[A[]][][] = ;
while(!Q.empty())
{
q1 = Q.front();
if(match(q1, B[], B[], B[])) return q1.step;
for(int i = ; i < ; ++ i) // 倒水的方式有6种
{
for(int j = ; j < ; ++ j)
{
if(i == j) continue;
int my_op = min(q1.temp[i], A[j] - q1.temp[j]); // 将i杯子里面的水倒到j杯子中
q2 = q1;
q2.temp[i] = q1.temp[i] - my_op;
q2.temp[j] = q1.temp[j] + my_op;
q2.step ++;
if(!book[q2.temp[]][q2.temp[]][q2.temp[]])
{
book[q2.temp[]][q2.temp[]][q2.temp[]] = ;
Q.push(q2);
}
}
}
Q.pop();
}
return -;
} int main()
{
int t;
scanf("%d", &t);
while(t --)
{
memset(book, , sizeof(book));
scanf("%d%d%d", &A[], &A[], &A[]);
scanf("%d%d%d", &B[], &B[], &B[]);
printf("%d\n", bfs());
}
return ;
}