三个水杯
时间限制：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
原题出自：http://acm.nyist.net/JudgeOnline/problem.php?pid=21 简单的宽度优先搜索，三个水杯之间的相互倒水如下图6种情况：对于每一次倒水都会引起三个水杯水量状态的改变，这样就可以得到如下的一个解空间树：
代码一：比较容易想到的
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstdlib>
using namespace std; int v1, v2, v3;
bool visit[][][]; //状态是否出现 struct state
{
int a, b, c;
int ceng; //最小步数
}b, e; int BFS()
{
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 > && 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 > && 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 > && 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 > && 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 > && 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 > && 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 -; //没有终状态
} int main()
{
int n;
scanf("%d", &n);
while(n--)
{
memset(visit, false, sizeof(visit));
scanf("%d %d %d", &v1, &v2, &v3);
b.a = v1, b.b = , b.c = , b.ceng = ;
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());
}
return ;
}方法二：Floyd 算法
Floyd 算法介绍：http://www.cnblogs.com/orange1438/p/4054649.html
#include <cstdio>
#include <memory.h>
#include <queue> using namespace std; #define EMPTY 0 struct data_type
{
int state[];
int step;
}; int cupCapacity[], targetState[]; bool visited[][][]; bool AchieveTargetState(data_type current)
{
for (int i = ; i < ; i++)
{
if (current.state[i] != targetState[i])
{
return false;
}
}
return true;
} void PourWater(int destination, int source, data_type &cup)
{
int waterYield = cupCapacity[destination] - cup.state[destination];
if (cup.state[source] >= waterYield)
{
cup.state[destination] += waterYield;
cup.state[source] -= waterYield;
}
else
{
cup.state[destination] += cup.state[source];
cup.state[source] = ;
}
} int BFS(void)
{
int i, j, k;
data_type initial;
queue<data_type> toExpandState; memset(visited, false, sizeof(visited));
initial.state[] = cupCapacity[];
initial.state[] = initial.state[] = ;
initial.step = ;
toExpandState.push(initial);
visited[initial.state[]][][] = true; while (!toExpandState.empty())
{
data_type node = toExpandState.front();
toExpandState.pop();
if (AchieveTargetState(node))
{
return node.step;
}
for (i = ; i < ; i++)
{
for (j = ; j < ; j++)
{
k = (i+j)%;
if (node.state[i] != EMPTY && node.state[k] < cupCapacity[k])
{
data_type newNode = node;
PourWater(k, i, newNode);
newNode.step = node.step + ;
if (!visited[newNode.state[]][newNode.state[]][newNode.state[]])
{
visited[newNode.state[]][newNode.state[]][newNode.state[]] = true;
toExpandState.push(newNode);
}
}
}
}
}
return -;
} int main(void)
{
int testNum;
scanf("%d", &testNum);
while (testNum -- != )
{
scanf("%d%d%d", &cupCapacity[], &cupCapacity[], &cupCapacity[]);
scanf("%d%d%d", &targetState[], &targetState[], &targetState[]);
printf("%d\n", BFS());
}
return ;
}