题目描述
n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数n,请你输出所有的满足条件的棋子摆法。
暴力枚举:按照行枚举
时间复杂度:$N·N!$
需要注意
(1)存在不同的枚举方式:按照每个位置进行枚举(复杂度比较高)/按照行进行枚举(复杂度相对比较低)
(2)枚举的过程中需要保证包含所有的方案
(3)对角线的枚举方法分为正对角线和反对角线
C++代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=10;
bool col[N],dg[2*N],udg[2*N];
char g[N][N];
int n;
void dfs(int u)
{
if(u==n){
for(int i=0;i<n;i++)printf("%s\n",g[i]);
puts("");
return;
}
for(int i=0;i<n;i++){
if(!col[i] && !dg[u+i] && !udg[n-u+i]){
col[i]=dg[u+i]=udg[n-u+i]=true;
g[u][i]='Q';
dfs(u+1);
g[u][i]='.';
col[i]=dg[u+i]=udg[n-u+i]=false;
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
g[i][j]='.';
dfs(0);
return 0;
}
你这时间不是 N! 吗?哪来的 N*N! ?