HDU 2553 N皇后问题

题目描述：给你一个N,表示有一个N*N的棋盘，现在要在棋盘上摆放N个皇后，为了使这N个皇后不互相攻击，要求是这N个皇后中任意两个皇后不能在同一行也不能在同一列，也不能在同一个45度角的斜线上，输入一个N,问，一共有多少中排列的方法。

解题报告：要判断有多少中方法，我们可以有几种选择，第一种，列出N*N的所有子集，然后逐一判断每个子集是否满足条件，然而这样的计算量显然太大，第二种，在N*N个格子里面选N个格子，也就是选N个格子出来进行排列，这样计算量还是太大，第三种，很显然，每一行或者每一列都只有一个皇后，现在我们确定每一行只有一个皇后，所以接下来我们只要确定每一行中的皇后排在那一列，这样，我们只需要枚举每一列的全排列，计算量一下子降到N！，但是这样当N=10的时候计算量仍然是10！，但是我们很自然的想到，这题的N最大只有10，所以一共只有10个，所以我们可以先将这10个答案离线打表，这样就OK了。离线运算的代码如下：

#include<cstdio>
#include<cmath>
#include<cstring>
const int SIZE = 15;
int tot;
bool judge(int n,int* A) {
 for(int i = 1;i<=n;++i)
 for(int j = i+1;j<=n;++j)
 if((A[i] == A[j])||(abs(i-j) == abs(A[i]-A[j])))
 return false;
 return true;
}
void dfs(int n,int* A,int deep) {
 if(n==deep-1)
 tot += judge(n,A);
 else for(int i = 1;i<=n;++i) {
  A[deep] = i;
  dfs(n,A,deep+1);
 }
}
int main() {
 int n,A[SIZE];
 while(scanf("%d",&n)!=EOF) {
  tot  = 0;
  memset(A,0,sizeof(A));
  dfs(n,A,1);
  printf("%d ",tot);
 }
 return 0;
}

提交代码也附上：

#include<cstdio>
int list[11] = {0,1,0,0,2,10,4,40,92,352,724};
int main() {
    int n;
    while(scanf("%d",&n)&&n)
    printf("%d
",list[n]);
    return 0;
}