#include<iostream>
#include<fstream>
using namespace std;

int num_count_best=27;
int bestnum[9]={3,3,3,3,3,3,3,3,3};
int m[9][9]=
{
	1,1,0,1,1,0,0,0,0,
	1,1,1,0,0,0,0,0,0,
	0,1,1,0,1,1,0,0,0,
	1,0,0,1,0,0,1,0,0,
	0,1,0,1,1,1,0,1,0,
	0,0,1,0,0,1,0,0,1,
	0,0,0,1,1,0,1,1,0,
	0,0,0,0,0,0,1,1,1,
	0,0,0,0,1,1,0,1,1
};


//int mincost=999999999;
void count_c(const int *num)
{
	int num_count=0;
	int i;
	for(i=0;i<9;i++)
	{
		num_count+=num[i];
	}
	if(num_count<num_count_best)
	{
		for(i=0;i<9;i++)
		{
			bestnum[i]=num[i];
		}
		num_count_best=num_count;
		//fout<<"p";
		return;
	}
	else if(num_count>num_count_best)
		return;
	else
	{
		bool flag=false;
		for(i=0;i<9;i++)
		{
			if(num[i]<bestnum[i])
			{
				flag=true;
				break;
			}
			else if(num[i]>bestnum[i])
			{
				return;
			}
		}
		if(flag)
		{
			for(i=0;i<9;i++)
			{
				bestnum[i]=num[i];
			}
			num_count_best=num_count;
			//fout<<"p";
			return;
		}
	}

}

void aaa(int *a,int *num,const int d,const int t)
{
	if(d>num_count_best)return;
	int i,j,k,flag=1;
	int b[9],bnum[9];
	for(k=0;k<9;k++)
	{
		bnum[k]=num[k];
	}
	for(k=0;k<9;k++)
	{
		if(a[k])
		{
			flag=0;
			break;
		}
	}
	if(flag)
	{
		count_c(bnum);
	}
	else
	{
		//cost*=10;
		for(i=t;i<9;i++)
		{
			//cost++;
			for(k=1;k<9;k++)
			{
				b[k]=a[k];	
			}
			for(j=0;j<9;j++)
			{
				b[j]+=m[i][j];
				b[j]%=4;
				//cout<<b[j];
			}
			bnum[i]++;
			if(i>t)bnum[i-1]--;
			//cout<<endl;
			//cout<<cost<<endl;
			//getchar();
			//dfs(b,cost,d*10);
			if(bnum[i]<4)aaa(b,bnum,d+1,i);
			else return;
		}
	}
}
int main()
{
	ifstream fin("clocks.in");
	ofstream fout("clocks.out");
	int temp,c[9],n[9]={0,0,0,0,0,0,0,0,0};
	int i;
	for(i=0;i<9;i++)
	{
		cin>>c[i];
		//cout<<clock[i]<<endl;
	}
	aaa(c,n,0,0);//这个函数一直不执行，不晓得为什么？
	//cout<<mincost<<endl;
	//fout<<num_count_best<<endl;
	for(i=0;i<9;i++)
	{
		while(bestnum[i])
		{
			cout<<i+1;
			bestnum[i]--;
			num_count_best--;
			if(num_count_best)cout<<' ';
			else cout<<endl;
		}	
	}
	//printf("%I64d\n",mincost);
	return 0;
}

• Re:BFS，为什么自己机子（SP3+VC++6.0）已经可以了，在OJ在死活就是过不了。搞了一整天，快崩溃了 (15) robertlzc 2011-01-10 15:27:22