1495 非常可乐.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

#include <cstdio>
#include <memory>
#include <queue>
using namespace std;

bool v[110][110][110];
int c[3],tmin,avg;
struct inf
{
	int b[3];
	int time;

	bool fill(int f,int t)
	{
		int left;

		if(b[t]>=c[t] || v[ b[0] ][ b[1] ][ b[2] ] || b[f]==0)
			return false;
		else
		{
			left=c[t]-b[t];
			if(b[f]>=left)
			{
				b[f]-=left;
				b[t]=c[t];
			}
			else
			{
				b[t]+=b[f];
				b[f]=0;
			}
			time++;
			//v[ b[0] ][ b[1] ][ b[2] ]=true;
			return true;
		}
	}

	bool isOK()
	{
		return ((b[0]==avg && b[1]==avg) || (b[0]==avg && b[2]==avg) || (b[1]==avg && b[2]==avg));
	}
};
queue<inf> SQ;

void bfs()
{
	inf tt,t2;

	while(!SQ.empty())
	{
		tt=SQ.front();
		SQ.pop();
		if(tt.isOK())
		{
			tmin=tt.time;
			return ;
		}
		else
		{
			t2=tt;
			if( t2.fill(0,1) )
				SQ.push(t2);

			t2=tt;
			if( t2.fill(1,0) )
				SQ.push(t2);

			t2=tt;
			if( t2.fill(0,2) )
				SQ.push(t2);

			t2=tt;
			if( t2.fill(2,0) )
				SQ.push(t2);

			t2=tt;
			if( t2.fill(1,2) )
				SQ.push(t2);

			t2=tt;
			if( t2.fill(2,1) )
				SQ.push(t2);
		}
		v[ tt.b[0] ][ tt.b[1] ][ tt.b[2] ]=true;
	}
}

int main()
{
	int i;
	inf it;

	while(scanf("%d %d %d",&c[0],&c[1],&c[2])==3)
	{
		if(c[0]==0 && c[1]==0 && c[2]==0)
			return 0;
		if(c[0]%2==1)
		{
			printf("NO\n");
		}
		else
		{
			memset(v,0,sizeof(v));
			//v[c[0]][0][0]=true;
			it.b[0]=c[0];
			it.b[1]=it.b[2]=it.time=0;
			tmin=0x7ffffff;
			avg=c[0]/2;

			while(!SQ.empty())
				SQ.pop();
			SQ.push(it);

			bfs();

			if(tmin!=0x7ffffff)
				printf("%d\n",tmin);
			else
				printf("NO\n");
		}
	}
}