checker.cpp

USACO chapter one.May hope it useful to someone

/*
ID: chenkai4
PROG: checker
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream in("checker.in");
ofstream out("checker.out");
int N;
bool c1[27]={0},c2[27]={0};
int sp=0,ans[3][14]={0};int fucksp=0;
bool state[14]={0};int determin[14]={0};int fuck;
#define Min(A,B) (A<B?A:B)


void search1(int n)
{
	if(n==N/2+1||n==fuck)
		search1(n+1);
	else if(n==N+1)
		sp++;
	else
	{
		for(int a=1;a<=N;a++)
		{
			if((!state[a])&&(!c1[n+a-1])&&(!c2[N-a+n]))
			{
				c1[n+a-1]=true;
				c2[N-a+n]=true;
				//determin[n]=1<<(N-a);
				state[a]=true;
				search1(n+1);
				state[a]=false;
				c1[n+a-1]=false;
				c2[N-a+n]=false;
			}
		}
	}
}

void search2(int n)
{
	if(n==N+1)
		sp++;
	else
	{
		int maxa=N;
		if(n==1)
			maxa=N/2;
		for(int a=1;a<=maxa;a++)
		{
			if((!state[a])&&(!c1[n+a-1])&&(!c2[N-a+n]))
			{
				c1[n+a-1]=true;
				c2[N-a+n]=true;
				//determin[n]=1<<(N-a);
				state[a]=true;
				search2(n+1);
				state[a]=false;
				c1[n+a-1]=false;
				c2[N-a+n]=false;
			}
		}
	}
}

void search3st(int n)
{
	if(fucksp<3)
	{
		if(n==N+1)
		{
			fucksp++;
			out<<determin[1];
			for(int a=2;a<=N;a++)
				out<<" "<<determin[a];
			out<<endl;
		}
		else
		{
			for(int a=1;a<=N;a++)
			{
				if((!state[a])&&(!c1[n+a-1])&&(!c2[N-a+n]))
				{
					c1[n+a-1]=true;
					c2[N-a+n]=true;
					determin[n]=a;
					state[a]=true;
					search3st(n+1);
					if(fucksp==3)
						return;
					state[a]=false;
					c1[n+a-1]=false;
					c2[N-a+n]=false;
				}
			}
		}
	}
}

void searchnum()
{
	if(N%2==0)
	{
		search2(1);
		sp*=2;
	}
	else
	{
		state[N/2+1]=true;
		for(int a=1;a<N/2;a++)
		{
			c1[N/2+a]=true;
			c2[N-a+N/2+1]=true;
			state[a]=true;
			for(int b=a+1;b<=N/2;b++)
			{
				fuck = b;
				c1[b+N/2]=true;
				c2[N-(N/2+1)+b]=true;
				search1(1);
				c1[b+N/2]=false;
				c2[N-(N/2+1)+b]=false;
			}
			c1[N/2+a]=false;
			c2[N-a+N/2+1]=false;
			state[a]=false;
		}
		sp*=8;

		c1[N]=true;
		c2[N]=true;
		fuck = N/2+1;
		search1(1);

	}
}
int main()
{
	in>>N;
	searchnum();
	for(int a=1;a<=N;a++)
		state[a]=false;
	for(int a=1;a<=N+N-1;a++)
	{c1[a]=false;c2[a]=false;}
	search3st(1);
	out<<sp<<endl;
	return 0;
}