nyoj 21--三个水杯（隐式图bfs）

三个水杯

时间限制：1000 ms | 内存限制：65535 KB

难度：4

描述

给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。

输入

第一行一个整数N(0<N<50)表示N组测试数据

接下来每组测试数据有两行，第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三个水杯的体积。

第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态

输出

每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1

样例输入

样例输出

3

-1

/*头一次看到隐式图，跟一般的bfs有一些不一样，不会直接给你图，具体见代码*/

#include<stdio.h>

#include<string.h>

#include<queue>

using namespace std;

int a[3],temp[3],map[1001][1001];

struct node

{

	int v[3];

	int step;

};

void bfs()

{

	memset(map,0,sizeof(map));//标记数组清零

	queue<node>q;

	node b,c;

	b.v[0]=a[0];

	b.v[1]=b.v[2]=b.step=0;

	q.push(b);

	map[0][0]=0;//初始化结构体和数组

	while(!q.empty())

	{

		c=q.front();

		q.pop();

		for(int i=0;i<3&&c.v[i]>=0;i++)

		//通过c.v可以去除小于零的体积 ，不过这好像不会出现

		{

			for(int j=0;j<3;j++)

			{

				b=c;

				if(i!=j)//不能对相同的水杯进行操作

				{

					if(b.v[0]==temp[0]&&b.v[1]==temp[1]&&b.v[2]==temp[2])

					{//达到目标体己的话就输出

						printf("%d\n",b.step);

						return ;

					}

					b.step=c.step+1;

					if(b.v[i]+b.v[j]<a[j])

					//搜索就是列举所有的情况，遇到合适的就输出，这一步就是列举

					//i和j中的水加起来如果小于j的体积，就可以直接倒在j中，但是i要清零

					{

						b.v[j]=b.v[i]+b.v[j];

						b.v[i]=0;

					}

					else

					//i和j中的水加起来如果大于j的体积，j满而且i中还有水

					{

						b.v[i]=b.v[i]+b.v[j]-a[j];

						b.v[j]=a[j];

					}

					if(map[b.v[1]][b.v[2]]==0)

					//因为有三个杯子，而且水的总量已知，那么只需要确定1,2的状态是否到达过

					{

						if(b.v[0]==temp[0]&&b.v[1]==temp[1]&&b.v[2]==temp[2])

						{

							printf("%d\n",b.step);

							return ;

						}//输出最小的步数，也可以设置一个优先队列，这样的话效率应该会高一些

						q.push(b);

						map[b.v[1]][b.v[2]]=1;

					}

				}

			}

		}

	}

	printf("-1\n");

}

int main()

{

	int n;

	scanf("%d",&n);

	while(n--)

	{

		scanf("%d%d%d",&a[0],&a[1],&a[2]);//每个杯子的体积还有目标体积

		scanf("%d%d%d",&temp[0],&temp[1],&temp[2]);

		bfs();

	}

}

巴特西

nyoj 21--三个水杯（隐式图bfs）

三个水杯

最新文章

热门文章