HDU 2553 N皇后问题

题目链接：传送门

Problem Description

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

Output

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input

1
8
5
0

Sample Output

1
92
10

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int m[15][15];
int x[15],y[15],n[15];
int s,w,z;
bool judge(int a,int b)
{
	if(x[a]!=0)
		return false;
	if(y[b]!=0)
		return false;
	int i,j;
	for(i=a+1,j=b+1;i<s&&j<s;i++,j++)
	{
		if(m[i][j])
			return false;
	}
	for(i=a+1,j=b-1;i<s&&j>=0;i++,j--)
	{
		if(m[i][j])
			return false;
	}
	for(i=a-1,j=b+1;i>=0&&j<s;i--,j++)
	{
		if(m[i][j])
			return false;
	}
	for(i=a-1,j=b-1;i>=0&&j>=0;i--,j--)
	{
		if(m[i][j])
			return false;
	}
	return true;
}
void dfs(int a)
{
	if(a==s)
	{
		w++;
		return ;
	}
	for(int i=0;i<s;i++)
	{
		if(judge(a,i))
		{
			m[a][i]=1;
			y[i]=1;
			x[a]=0;
			dfs(a+1);
			m[a][i]=0;
			y[i]=0;
			x[a]=0;
		}
	}
}
int main()
{
	int a,b,c,d,e,f;
	for(s=1;s<12;s++)
	{
		memset(x,0,sizeof(x));
		memset(m,0,sizeof(x));
		memset(y,0,sizeof(x));
		x[0]=1;
		w=0;
		for(a=0;a<s;a++)
		{
			m[0][a]=1;
			y[a]=1;
			dfs(1);
			m[0][a]=0;
			y[a]=0;
		}
		n[s]=w;
	}
	while(cin>>a)
	{
		if(a==0)
			break;
		cout<<n[a]<<endl;
	}
	return 0;
}