checker.cpp

USACO Section 1-4的后两个程序以及Section 1-5的全部程序代码

/*
NAME:lemon_c1
LANG:C++
PROG:checker
*/
#include<fstream>
using namespace std;
ifstream cin("checker.in");
ofstream cout("checker.out");
int pos[14];
int rows[14];
void dfs(int row);
int n;
int sol;
int tsol;
int toand;
inline void swap(int &t1,int &t2)
{
	int t=t1;
	t1=t2;
	t2=t;
}
inline int abs1(int t1)
{
	return t1<0?-t1:t1;
}
bool cons(int row,int col)
{
	for(int i=0;i<row;i++)
		if(abs1(col-pos[i])==row-i)return false;
	return true;
}
int main(void)
{
	cin>>n;
	for(int i=1;i<=n;i++)
		pos[i-1]=i;
	toand=1<<n;
	toand--;
	dfs(0);
	cout<<sol<<endl;
	return 0;
}
void dfs2(int layer)
{
	if(layer==n)
	{
		sol++;
		return;
	}
	int cons=0;
	for(int i=0;i<layer;i++)
		cons|=rows[i]|rows[i]<<(layer-i)|rows[i]>>(layer-i);
	if(~cons&toand==0)return;
	cons&=toand;
	rows[layer]=1;
	for(int i=0;i<n;i++)
		if(((cons>>i)&1)==0)
		{
			rows[layer]<<=i;
			dfs2(layer+1);
			rows[layer]>>=i;
		}
}
void dfs(int row)
{
	if(row==n)
	{
		sol++;
		if(sol<4)
		{
			cout<<pos[0];
			for(int i=1;i<n;i++)
				cout<<' '<<pos[i];
			cout<<endl;
		}
		else
		{
			sol=0;
			int tsol=0;
			for(int i=0;i<n/2;i++)
			{
				rows[0]=1<<i;
				dfs2(1);
				tsol+=sol*2;
				sol=0;
			}
			if(n&1)
			{
				rows[0]=1<<(n/2);
				dfs2(1);
				tsol+=sol;
				sol=0;
			}
			cout<<tsol<<endl;
			exit(0);
		}
		return;
	}
	for(int i=row;i<n;i++)
	{
		swap(pos[i],pos[row]);
		if(cons(row,pos[row]))
			dfs(row+1);
		swap(pos[i],pos[row]);
	}
}