三明市建设局网站天津seo招聘

题目

来源

843. n-皇后问题 - AcWing题库

思路

引自：AcWing 843. n-皇后问题--图解+代码注释 - AcWing

核心思路：深度优先遍历

函数名：void dfs(int r): 深度优先遍历函数。参数r：从第r行开始放棋子，处理第r行。

递归结束判定：见代码，当 r == n的时候，说明应该处理第 n行了，也代表第 0~n-1行放好棋子，也就是整个棋盘放好了棋子，也就是得到了一种解，也就是递归结束。

第r行，第i列能不能放棋子：用数组dg udg cor 分别表示：点对应的两个斜线以及列上是否有皇后。
dg[i + r] 表示 r行i列处，所在的对角线上有没有棋子，udg[n - i + r]表示 r行i列处，所在的反对角线上有没有棋子，cor[i]表示第i列上有没有棋子。如果 r行i列的对角线，反对角线上都没有棋子，即!cor[i] && !dg[i + r] && !udg[n - i + r]为真，则代表 r行i列处可以放棋子。

 n - i + r和i + r其实就是一个小trick，b=y-x或者b=y+x；+n是为了防止出现负数越界

代码

#include<bits/stdc++.h>
using namespace std;
const int N=20;
char dg[N],udg[N],col[N];
char q[N][N];
// int r; //表示每行，一行一行去处理
int n;
void dfs(int r){if(r==n){for(int i=0;i<n;i++){for(int j=0;j<n;j++){cout<<q[i][j];}cout<<endl;            }cout<<endl;return;}for(int i=0;i<n;i++){if(!col[i]&& !dg[i+r] && !udg[n-i+r]){q[r][i]='Q';col[i]=dg[i+r]=udg[n-i+r]=1;dfs(r+1);col[i]=dg[i+r]=udg[n-i+r]=0;q[r][i]='.'; //这里也是要恢复现场的}}}
int main(){cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){q[i][j]='.';}}dfs(0);return 0;
}