18124 N皇后问题
时间限制:2000MS 内存限制:65535K
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC;VC
Description
有N*N的国际象棋棋盘，要求在上面放N个皇后，要求任意两个皇后不会互杀，有多少种不同的放法？
输入格式
每一个数为T，代表CASE的数量，T<=13
此后，每行一个数N（13>=N>0）
输出格式
每一个CASE，输出对应答案
输入样例
2
4
5
输出样例
2
10
//排列问题 关键在于 while( n-- ) { if(**) 递归 ;} if是为了适应特殊要求的数字序列
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
using namespace std;
void All(int T[],int n,int cur ,int &a) //cur 代表 第cur+1 列 共n列
{
if(cur==n) a++; //cur==n 说明有一个符合要求的数字序列
else for(int i=0;i<n;i++)
{
int sig=1;
for(int j=0;j<cur;j++) if(T[j]==i) {sig=0;break;} //用来限制 数字序列不在同一行
for(int j=0;j<cur;j++) if(abs(i-T[j])==abs(cur-j)) {sig=0;break;}//第j列 不会和 第cur列 斜杀
if(sig)//符合两个条件 才进行 下一列的 递归
{
T[cur]=i;
All(T,n,cur+1,a);
}
}
}
int main()
{
int n,m,T[13],Count;
cin>>n;
while(n--)
{
cin>>m;
Count=0;//共有多少可能 初始化 0
All(T,m,0,Count);
cout<<Count<<endl;
}
}
