HDU 1495 非常可乐(隐式图的遍历)

2015年7月26日 10点热度 0条评论 来源: _天道酬勤_不忘初心

题目地址:点击打开链接

思路:用3维数组标记已走过的点,其实没有必要,因为2个杯中的水确定下来,剩下的一个点也就确定下来了,只用一个2维数组标记即可

这道题是一个一般隐式图的遍历

说到底就是搜索问题,把各种状态都走一遍,直到走到要的那种状态,用数组标记已走过的状态,如果走过就不用进队了,要是你非要进,只会浪费时间

状态转移无非6种情况

S->N

S->M

N->M

N->S

M->S

M->N;

AC代码:

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int a[5],visit[110][110],sum;
struct cf
{
	int v[3];
	int step;
}x,xx;
void bfs()
{
	int i,j;
	queue<cf> q;
	x.v[0] = a[0];
	x.v[1] = 0;
	x.v[2] = 0;
	x.step = 0;
	q.push(x);
	visit[0][0] = 0;
	while(!q.empty())
	{
		sum = 0;
		x = q.front();
		q.pop();
		if(x.v[0] == a[0] / 2)
			sum++;
		if(x.v[1] == a[0] / 2)
			sum++;
		if(x.v[2] == a[0] / 2)
			sum++;
		if(sum == 2)
		{
			printf("%d\n",x.step);
				return;
		}
		for(i=0; i<3; i++)//从i往j中倒水
		{
			if(x.v[i] > 0)//i中没水就不用倒了
			{
				for(j=0; j<3; j++)
				{
					if(i == j)//i和j是一个杯子也不用倒
						continue;
					xx = x;
					if(xx.v[i] + xx.v[j] > a[j])//i杯和j杯中原来的水比j杯的体积大,所以j杯倒满,i杯还有一点水
					{
						xx.v[i] -= a[j] - xx.v[j];//i杯中剩下的水,
						xx.v[j] = a[j];//j杯倒满水,2句代码的次序不能错
					}
					else
					{
						xx.v[j] += xx.v[i]; //i杯和j杯中原来的水比j杯的体积小或者等于,所以j杯的水比j杯的体积小或者等于
						xx.v[i] = 0;//杯中没水了
					}
					if(!visit[ xx.v[1] ][ xx.v[2] ])
					{
						visit[ xx.v[1] ][ xx.v[2] ] = 1;//标记已走过的状态
						xx.step = x.step + 1;
						q.push(xx);
					}
				}
			}
		}
	}
	printf("NO\n");
}
						
int main()
{
	while(scanf("%d%d%d",&a[0],&a[1],&a[2]))
	{
		memset(visit,0,sizeof(visit));
		if(a[0] + a[1] + a[2] == 0)
			break;
		if(a[0] % 2 != 0)//不是偶数直接退出就行,不然BFS会输出错误的步数
			printf("NO\n");
		else
			bfs();
	}
	return 0;
}

    原文作者:_天道酬勤_不忘初心
    原文地址: https://blog.csdn.net/qq_25605637/article/details/47070597
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。