出处：
http://acm.nyist.net/JudgeOnline/problem.php?pid=21三个水杯
时间限制：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<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdlib>
using namespace std;
int total;
int v1, v2, v3;
bool visit[105][105][105]; //状态是否出现
struct state
{
int a, b, c;
int ceng; //最小步数
state(){
a = b = c = ceng = 0;
}
}b, e;
int BFS(state begin)
{
queue<state> q;
while(!q.empty())
q.pop();
q.push(b);
while(!q.empty())
{
state cur = q.front();
q.pop();
visit[cur.a][cur.b][cur.c] = true;
if(cur.a == e.a && cur.b == e.b && cur.c == e.c) //找到
return cur.ceng;
if(cur.a > 0 && cur.b < v2) //v1->v2
{
state temp = cur;
int tt = min(temp.a, v2 - temp.b);
temp.a -= tt;
temp.b += tt;
if(visit[temp.a][temp.b][temp.c] == false)
{
visit[temp.a][temp.b][temp.c] = true;
temp.ceng++;
q.push(temp);
}
}
if(cur.a > 0 && cur.c < v3) //v1->v3
{
state temp = cur;
int tt = min(temp.a, v3 - temp.c);
temp.a -= tt;
temp.c += tt;
if(visit[temp.a][temp.b][temp.c] == false)
{
visit[temp.a][temp.b][temp.c] = true;
temp.ceng++;
q.push(temp);
}
}
if(cur.b > 0 && cur.a < v1) //v2->v1
{
state temp = cur;
int tt = min(temp.b, v1 - temp.a);
temp.a += tt;
temp.b -= tt;
if(visit[temp.a][temp.b][temp.c] == false)
{
visit[temp.a][temp.b][temp.c] = true;
temp.ceng++;
q.push(temp);
}
}
if(cur.b > 0 && cur.c < v3) //v2->v3
{
state temp = cur;
int tt = min(temp.b, v3 - temp.c);
temp.b -= tt;
temp.c += tt;
if(visit[temp.a][temp.b][temp.c] == false)
{
visit[temp.a][temp.b][temp.c] = true;
temp.ceng++;
q.push(temp);
}
}
if(cur.c > 0 && cur.a < v1) //v3->v1
{
state temp = cur;
int tt = min(temp.c, v1 - temp.a);
temp.c -= tt;
temp.a += tt;
if(visit[temp.a][temp.b][temp.c] == false)
{
visit[temp.a][temp.b][temp.c] = true;
temp.ceng++;
q.push(temp);
}
}
if(cur.c > 0 && cur.b < v2) //v3->v2
{
state temp = cur;
int tt = min(temp.c, v2 - temp.b);
temp.c -= tt;
temp.b += tt;
if(visit[temp.a][temp.b][temp.c] == false)
{
visit[temp.a][temp.b][temp.c] = true;
temp.ceng++;
q.push(temp);
}
}
}
return -1; //没有终状态
}
int main()
{
int ncase;
scanf("%d", &ncase);
while(ncase--)
{
total = 0;
memset(visit, false, sizeof(visit));
scanf("%d %d %d", &v1, &v2, &v3);
b.a = v1, b.b = 0, b.c = 0, b.ceng = 0;
scanf("%d %d %d", &e.a, &e.b, &e.c);
if(v1 < e.a + e.b + e.c)
{
printf("-1\n");
continue;
}
else
printf("%d\n", BFS(b));
}
return 0;
}posted on 2014-10-05 14:18
龙在江湖 阅读(257)
评论(0) 编辑 收藏 引用 所属分类:
搜索