【搜索与回溯算法】N皇后问题 (Standard IO)
【搜索与回溯算法】N皇后问题 (Standard IO)
题目描述
在一个nXn的国际象棋棋盘上放置n(n<=12)个皇后，使它们不能互相攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）。试求出所有方法。
输入
输入一个数n .(n<=12)
输出
输出所有的排列方案总数。
样例输入
4样例输出
2
基础dfs，重要的是标记数组；
标记数组思路：定义bool类型的3个数组，分别存储列，左对角线，右对角线；列很好存储，但左对角线，右对角线怎么一瞬间用O(1)的复杂度把两个对角线上的所有元素标记为1呢？
找规律可以发现：
左对角线规律：设当前的格子坐标为(i，j)则当前对角线所有元素的差值为0，即i-j==0但i-j这个下标可能为负数，尽人皆知数组下标不可能出现负数的情况，所以我们不妨把下标统一加(n-1)，这样即可保证下表不会是负数，又可以在瞬间把整条对角线标记复杂度很低
右对角线规律：同理，设当前格子坐标为（i，j)则当前对角线的i+j始终相等；
故可以写出如下代码:
#include<cstdio>
using namespace std;
int n,ans,a[110];
bool b[110],c[110],d[110];
void dfs(int i){//在第i行放置皇后
if(i>n){//到达搜索边界
ans++;//方案++；
return;
}
for(int j=1;j<=n;j++){//枚举每一行中的列
if(b[j]==0&&c[i+j]==0&&d[i-j+n-1]==0){//不会被已经放置的皇后攻击到
b[j]=c[i+j]=d[i-j+n-1]=1;//宣布占领
a[i]=j;//在第i行中标记了在第j列放置皇后
dfs(i+1);//搜索下一层
b[j]=c[i+j]=d[i-j+n-1]=0;//回溯
}
}
}
int main(){
scanf("%d",&n);
dfs(1);
printf("%d",ans);
}