湖南郴州市地图_seo网站关键词优化报价_windows优化大师免费_百度推广开户费用

目录

题目描述

输入格式:

输出格式:

输入样例:

输出样例:

解题思路：

详细代码（dfs）：

简单代码（打表）：

---

题目描述

在N×N格的国际象棋盘上摆放N个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，对于给定的N，求出有多少种合法的放置方法。

输入格式:

一个正整数N≤10，表示棋盘和皇后的数量；

输出格式:

一个正整数，表示对应输入行的皇后的不同放置方法。

输入样例:

在这里给出一组输入。例如：

8

输出样例:

在这里给出相应的输出。例如：

92

解题思路：

从上到下从左到右开始遍历这个二维数组做的棋盘 

由于是从左到右的所以无需标记行是否放过

创建三个数组分别表示某一列，某一对角线，某一反对角线是否放过

为什么

对角线是y+x，反对角线是y-x+n

如图所示

同一对角线的值可以表示为y+x

同一反对角线的值可以表示为y-x

为什么y-x还要加n呢

因为y-x有可能为负数，数组的下标不能为负加上n保证一定为正数

详细代码（dfs）：

#include <iostream>
using namespace std;
const int N=20; 
int n;
bool col[N],dg[N],udg[N];
int sum=0;
void dfs(int u) {if(u==n){//如果到达最后一行记录答案sum++;return;}int x=u;for (int y=0;y<n;y++)  if (!col[y]&&!dg[y+x]&&!udg[y-x+n]){//如果这一列、对角线、反对角线都没放过col[y]=dg[y+x]=udg[y-x+n]=true;//标记为放过dfs(x+1);col[y]=dg[y+x]=udg[y-x+n]=false;//回溯即刚刚放的标记为没放过}
}
int main() 
{cin>>n;dfs(0);cout<<sum;return 0;
}  

简单代码（打表）：

如果你仅仅只是想过样例

#include<iostream>
using namespace std;
int sz[]={0,1,0,0,2,10,4,40,92,352,724};//提前将答案储存下来
int main()
{int n;cin>>n;cout<<sz[n];
}