NYOJ 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
原题出自:http://acm.nyist.net/JudgeOnline/problem.php?pid=21 简单的宽度优先搜索,三个水杯之间的相互倒水如下图6种情况:

NYOJ 21 三个水杯

对于每一次倒水都会引起三个水杯水量状态的改变,这样就可以得到如下的一个解空间树:

NYOJ 21 三个水杯

代码一:比较容易想到的

 #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 ;
}

部分转自:http://blog.csdn.net/code_pang/article/details/7802944

上一篇:【6】和作为连续序列s


下一篇:小代码编写神器:LINQPad 使用入门