lanqiaoOJ 1508：N皇后问题 ← dfs

【题目来源】
https://www.lanqiao.cn/problems/1508/learning/

【题目描述】
在 N×N 的方格棋盘放置了 N 个皇后，使得它们不相互攻击（即任意 2 个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成 45角的斜线上。你的任务是，对于给定的 N，求出有多少种合法的放置方法。

【输入格式】
输入中有一个正整数 N≤10，表示棋盘和皇后的数量。

【输出格式】
为一个正整数，表示对应输入行的皇后的不同放置数量。

【输入样例】
5

【输出样例】
10

【算法分析】
● 主对角线是棋盘中从左上到右下的斜线，主斜线 zxx[] 是棋盘中与主对角线平行的斜线。
观察易知，同一主斜线上各棋格的横坐标 x 减去纵坐标 y 的差相等。即说明同一主斜线上多个棋格可通过减法映射到数组中的同一位置。此时，若判断某条主斜线上是否出现过一次皇后，即查看 zxx[x - y] 是否为空即可。但这样做减法时可能会得到一个负数，是没法直接映射到数组中的，因此在主斜线上做判断时统一加上一个常量保证非负，即 zxx[x - y + n]。

● 副对角线是棋盘中从左下到右上的斜线，副斜线 fxx[] 是棋盘中与副对角线平行的斜线。
观察易知，同一副斜线上各棋格的横坐标 x 加上纵坐标 y 的和相等。即说明同一副斜线上多个棋格可通过加法映射到数组中的同一位置。此时，若判断某条副斜线上是否出现过一次皇后，即查看 fxx[x + y] 是否为空即可。
————————————————                       
原文链接：https://blog.csdn.net/hnjzsyjyj/article/details/148391039

【算法代码】
通过三个一维数组 (col,zxx,fxx) 替代二维数组检查，将空间复杂度从 O(N²) 降到O(N)，是 N 皇后问题的优化解法。

#include <bits/stdc++.h>
using namespace std;const int N=15;
char a[N][N];
bool zxx[N<<1],fxx[N<<1],col[N];
int n,ans;void dfs(int k) { //k:rowif(k==n) {ans++;return;}for(int i=0; i<n; i++) { //i:columnif(!col[i] && !fxx[i+k] && !zxx[n-i+k]) {col[i]=fxx[i+k]=zxx[n-i+k]=1;dfs(k+1);col[i]=fxx[i+k]=zxx[n-i+k]=0;}}
}int main() {cin>>n;dfs(0);cout<<ans<<endl;return 0;
}/*
in:5
out:10
*/

【参考文献】
https://www.lanqiao.cn/problems/1508/learning/
https://blog.csdn.net/hnjzsyjyj/article/details/148391039