milk3.cpp

USACO chapter one.May hope it useful to someone

/*
ID: chenkai4
PROG: milk3
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("milk3.in");
ofstream out("milk3.out");
int A,B,C;
bool hash[9262]={0};
int toI20[3]={1,21,441};
int state[20000],b=0,e=0;
bool canreach[21]={0};
int full[3]={0};
struct _int
{
	int l,b[3];
	_int(int n=0)
	{
		l=0;memset(b,0,sizeof(b));
		while(n)
		{
			b[l++]=n%21;
			n/=21;
			if(b[l])l++;
		}
	}
	int toInt()
	{
		return (b[0]*toI20[0]+b[1]*toI20[1]+b[2]*toI20[2]);
	}
};
void Initialize()
{
	in>>A>>B>>C;
	_int begin;
	begin.b[0]=begin.b[1]=0;begin.b[2]=C;
	state[0]=begin.toInt();
	hash[state[0]]=true;
	full[0]=A;full[1]=B;full[2]=C;
}
void search()
{
	while(b<=e)
	{
		int te=e;
		for(int a=b;a<=te;a++)
		{
			int t = state[a];
			_int tstate = t;
			if(tstate.b[0]==0)
				canreach[tstate.b[2]]=true;
			for(int i1=0;i1<=2;i1++)
				for(int i2=0;i2<=2;i2++)
					if(i1!=i2)
					{
						tstate = state[a];
						if(tstate.b[i2]!=full[i2]&&tstate.b[i1]!=0)
							if(tstate.b[i1]<=full[i2]-tstate.b[i2])
							{
								tstate.b[i2]+=tstate.b[i1];
								tstate.b[i1]=0;
								if(!hash[tstate.toInt()])
								{
									hash[tstate.toInt()]=true;
									e++;
									state[e]=tstate.toInt();
								}
							}
							else
							{
								tstate.b[i1]-=full[i2]-tstate.b[i2];
								tstate.b[i2]=full[i2];
								if(!hash[tstate.toInt()])
								{
									hash[tstate.toInt()]=true;
									e++;
									state[e]=tstate.toInt();
								}
							}
					}
		}
		b=te+1;
	}
}

int main()
{
	Initialize();
	search();
	int t=0,tt=0;
	for(int a=0;a<=20;a++)
		if(canreach[a])t++;
	for(int a=0;a<=20;a++)
	{
		if(canreach[a])
		{
			tt++;
			if(tt!=t)
				out<<a<<" ";
			else
				out<<a<<endl;
		}
	}
	return 0;
}