clocks.cpp

USACO chapter one.May hope it useful to someone

/*
ID: chenkai4
PROG: clocks
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("clocks.in");
ofstream out("clocks.out");

struct _int
{
	int l,b[10];
	_int(int n=0)
	{
		l=0;memset(b,0,sizeof(b));
		while(n)
		{
			b[l++]=n%4;
			n/=4;
			if(b[l])l++;
		}
	}
};

int state[1048576],b=0,e=0;bool hash[1048576]={0};
int from[1048576]={0};
char choose[1048576];
int d4[10]={1,4,16,64,256,1024,4096,16384,65536,262144};
int ToInt10(_int num)
{
	int answer=0;
	for(int a=0;a<9;a++)
		answer+=num.b[a]*d4[a];
	return answer;
}
void addnum(_int *num,int which)
{
	num->b[which] = (num->b[which]+1)%4;
}
int step[1000],sp=0;
int main()
{
	_int first;int t;first.l = 9;
	for(int a=0;a<9;a++)
	{in>>t;first.b[a]=(t/3)%4;}
	if(ToInt10(first)==0)
		return 0;
	state[0]=ToInt10(first);
	bool hasanswer=false;
	while(b<=e&&!hasanswer)
	{
		int te=e;
		for(int a=b;a<=te;a++)
		{
			if(state[a]==0)
			{
				hasanswer=true;
				int now = a;
				while(now!=0)
				{
					step[sp++]=choose[now];
					_int print = state[from[now]];
					now=from[now];
				}
				break;
			}
			_int thisone = state[a];
			_int tthisone = thisone;

			//State1
			addnum(&tthisone,0);
			addnum(&tthisone,1);
			addnum(&tthisone,3);
			addnum(&tthisone,4);
			if(!hash[ToInt10(tthisone)])
			{
				hash[ToInt10(tthisone)]=true;
				e++;
				state[e]=ToInt10(tthisone);
				choose[e]=1;
				from[e]=a;
			}

			//State2
			tthisone = thisone;
			addnum(&tthisone,0);
			addnum(&tthisone,1);
			addnum(&tthisone,2);
			if(!hash[ToInt10(tthisone)])
			{
				hash[ToInt10(tthisone)]=true;
				e++;
				state[e]=ToInt10(tthisone);
				choose[e]=2;
				from[e]=a;
			}

			//State3
			tthisone = thisone;
			addnum(&tthisone,1);
			addnum(&tthisone,2);
			addnum(&tthisone,4);
			addnum(&tthisone,5);
			if(!hash[ToInt10(tthisone)])
			{
				hash[ToInt10(tthisone)]=true;
				e++;
				state[e]=ToInt10(tthisone);
				choose[e]=3;
				from[e]=a;
			}

			//State4
			tthisone = thisone;
			addnum(&tthisone,0);
			addnum(&tthisone,3);
			addnum(&tthisone,6);
			if(!hash[ToInt10(tthisone)])
			{
				hash[ToInt10(tthisone)]=true;
				e++;
				state[e]=ToInt10(tthisone);
				choose[e]=4;
				from[e]=a;
			}

			//State5
			tthisone = thisone;
			addnum(&tthisone,1);
			addnum(&tthisone,3);
			addnum(&tthisone,4);
			addnum(&tthisone,5);
			addnum(&tthisone,7);
			if(!hash[ToInt10(tthisone)])
			{
				hash[ToInt10(tthisone)]=true;
				e++;
				state[e]=ToInt10(tthisone);
				choose[e]=5;
				from[e]=a;
			}
			
			//State6
			tthisone = thisone;
			addnum(&tthisone,2);
			addnum(&tthisone,5);
			addnum(&tthisone,8);
			if(!hash[ToInt10(tthisone)])
			{
				hash[ToInt10(tthisone)]=true;
				e++;
				state[e]=ToInt10(tthisone);
				choose[e]=6;
				from[e]=a;
			}

			//State7
			tthisone = thisone;
			addnum(&tthisone,3);
			addnum(&tthisone,4);
			addnum(&tthisone,6);
			addnum(&tthisone,7);
			if(!hash[ToInt10(tthisone)])
			{
				hash[ToInt10(tthisone)]=true;
				e++;
				state[e]=ToInt10(tthisone);
				choose[e]=7;
				from[e]=a;
			}

			//State8
			tthisone = thisone;;
			addnum(&tthisone,6);
			addnum(&tthisone,7);
			addnum(&tthisone,8);
			if(!hash[ToInt10(tthisone)])
			{
				hash[ToInt10(tthisone)]=true;
				e++;
				state[e]=ToInt10(tthisone);
				choose[e]=8;
				from[e]=a;
			}

			//State9
			tthisone = thisone;
			addnum(&tthisone,4);
			addnum(&tthisone,5);
			addnum(&tthisone,7);
			addnum(&tthisone,8);
			if(!hash[ToInt10(tthisone)])
			{
				hash[ToInt10(tthisone)]=true;
				e++;
				state[e]=ToInt10(tthisone);
				choose[e]=9;
				from[e]=a;
			}
		}
		b=te+1;
	}
	out<<step[sp-1];
	for(int a=sp-2;a>=0;a--)
		out<<" "<<step[a];
	out<<endl;
	return 0;
}