2834045_re.cpp

北大大牛代码 1240道题的原代码 超级权威

/*
ID: gw2gw2
PROG: clocks
LANG: C++
*/

#include <stdio.h>
#include <queue>
//#include <map>
//#include <string>
#include <algorithm>

using namespace std;

struct node
{
	short a[9];
	short len;
	short use[10];
	short way[29];
	////vector <int> way;
};

//map <string,int> h;
//string num;
//queue <node> que;
node que[50000];
int f, r;

char mov[][6] = {"","ABDE","ABC","BCEF","ADG","BDEFH","CFI","DEGH","GHI","EFHI"};
//string ans = "444444444";
int h[5][5][5][5][5][5][5][5][5];

void bfs()
{
	int i, j;
	//char ch;
	node t, q;
	//string tmp;

	while(f!=r)//!que.empty()
	{
		++f;
		t = que[f];
		//t = que.front();
		//que.pop();
		for(i = 1; i <= 9; i++)
		{
			q = t;
		/*	for(j = 0; j < 9; j++)
			{
				ch = 'A'+j;
				if(strchr(mov[i],ch))
					q.a[j]++;
				if(q.a[j]==5)
					q.a[j] = 1;	
			}*/
			for(j = 0; mov[i][j]!='\0'; j++)
			{
				q.a[mov[i][j]-'A']++;
				if(q.a[mov[i][j]-'A']==5)
					q.a[mov[i][j]-'A'] = 1;
			}
		//	q.way.push_back(i);
			q.way[q.len++] = i;
			q.use[i]++;
			if(q.use[i]>3)
				continue;
		//	tmp = "";
		//	for(j = 0; j < 9; j++)
		//	{
		//		ch = q.a[j]+'0';
		//		tmp += ch;
		//	}
			if(!h[q.a[0]][q.a[1]][q.a[2]][q.a[3]][q.a[4]][q.a[5]][q.a[6]][q.a[7]][q.a[8]])
			{
				h[q.a[0]][q.a[1]][q.a[2]][q.a[3]][q.a[4]][q.a[5]][q.a[6]][q.a[7]][q.a[8]] = 1;
			//	printf("%d\n",r);
				que[++r] = q;
			//	que.push(q);
			}
			if(h[4][4][4][4][4][4][4][4][4])
			{
				for(j = 0; j +1< q.len; j++)
					printf("%d ",q.way[j]);
				printf("%d\n",q.way[j]);
				return ;
			}
		}
	}
}

int main()
{
	int i;
//	char ch;
	node t;

//	freopen("clocks.in","r",stdin);
//	freopen("clocks.out","w",stdout);
//	num = "";
	for(i = 0; i < 9; i++)
	{
		scanf("%d",&t.a[i]);
		if(t.a[i]==0)
			t.a[i] = 4;
	}//,t.a[i]/=3;//,num += (ch=t.a[i]+'0');
//	t.way.clear();
	t.len = 0;
	memset(h,0,sizeof(h));
	h[t.a[0]][t.a[1]][t.a[2]][t.a[3]][t.a[4]][t.a[5]][t.a[6]][t.a[7]][t.a[8]] = 1;
	f = r = -1;
	memset(t.use,0,sizeof(t.use));
	////que.push(t);
	que[++r] = t;
	bfs();
	return 0;
}