USACO Section 1.5 Checker Challenge

/*
ID: lucien23
PROG: checker
LANG: C++
*/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int N;
int symPos;
int sum=0;
int count=0;
bool isCountComplete=false;
bool isPrintComplete=false;
int *position;

void generate(int row);

int main()
{
	freopen("checker.in","r",stdin);
	freopen("checker.out","w",stdout);

	scanf("%d",&N);
	symPos=N/2+N%2+1;
	position=(int*)malloc(N*sizeof(int));
	generate(0);
	printf("%d\n",sum);
	free(position);
	return 0;
}

void generate(int row)
{
	int *pPos=(int*)malloc(N*sizeof(int));
	for(int i=0;i<N;i++)
	{
		pPos[i]=0;
	}
	for (int i=0;i<row;i++)
	{
		pPos[position[i]]=1;
	}
	
	for(int i=0;i<N;i++)
	{//第row行的棋子放在第i列
		if(row==0)
		{
			if(N%2==0 && i==symPos-1)
			{//偶数列
				sum*=2;
				isCountComplete=true;
			}else if(N%2==1 && i==symPos-2){
				sum*=2;
			}else if (N%2==1 && i==symPos-1){
				isCountComplete=true;
			}
		}

		if(isCountComplete && isPrintComplete)
			return;

		if(pPos[i])
			continue;
		int k;
		for (k=0;k<row;k++)
		{
			if(abs(row-k)==abs(i-position[k]))
				break;
		}
		if(k<row)
		{//第row行的棋子不能放在第i列
			continue;
		}

		position[row]=i;
		if(row==N-1)
		{
			count++;
			if(!isCountComplete)
				sum++;
			if(count<=3)
			{
				for (int j=0;j<N-1;j++)
				{
					printf("%d ",position[j]+1);
				}
				printf("%d\n",position[N-1]+1);
				if(count==3)
					isPrintComplete=true;
			}
		}else{
			generate(row+1);
		}
	}
	free(pPos);
}

USACO Section 1.5 Checker Challenge,布布扣,bubuko.com

USACO Section 1.5 Checker Challenge

原文：http://blog.csdn.net/lucienduan/article/details/21482509