在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。 你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
1
8
5
0
Sample Output
1
92
10
这个题目是n皇后问题，需要用到深搜，但是时间限制为1s，好短啊，而且需要输入数据很多很多，所以当每次输入n时，调用dfs，每次又要运行dfs，会消耗很多时间，所以需要提前 打表（在输出和运用数据之间，需要提前处理，并且存到数组中，当等到使用的时候，直接调用数组下标来输出和使用，这样会节省大量的时间）；
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
int a[20];
int book[20];
int result[20];
int ans;
int n;
void dfs(int step)
{
if(step==n)
{
ans++;
return;
}
int i,k;
for(k=0;k<n;k++)///列数所有的情况进行尝试
{
if(book[k]==1)
continue;
book[k]=1;
a[step]=k;
for(i=0;i<step;i++)///行数和之前的行数和对应的列数，来判断当前填入的数和之前的数是否在一列或在45度对角线上
{
if(/*a[i]==a[step]||*/a[i]-i==a[step]-step||a[i]+i==step+a[step]){
book[k]=0;
break;
}
}
if(i==step){
dfs(step+1);///如果和前面的数没有冲突，那么进行下一行进行填数
book[k]=0;
}
}
}
int main()
{
for(n=1;n<=10;n++)///这部分就是打表，先把每个数字对应的n皇后共有多少种算出来，输出的时候就直接调用数组标。
{
memset(a,0,sizeof(a));
memset(book,0,sizeof(book));
ans=0;
dfs(0);
result[n]=ans;
}
while(~scanf("%d",&n)&&n)
{
printf("%d\n",result[n]);
}
}
’
转载请注明原文地址: https://www.6miu.com/read-60082.html
