Acwing算法基础课——843.n-皇后问题

题目n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上使得皇后不能相互攻击到即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数 n请你输出所有的满足条件的棋子摆法。输入格式共一行包含整数 n。输出格式每个解决方案占 n 行每行输出一个长度为 n 的字符串用来表示完整的棋盘状态。其中.表示某一个位置的方格状态为空Q表示某一个位置的方格上摆着皇后。每个方案输出完成后输出一个空行。注意行末不能有多余空格。输出方案的顺序任意只要不重复且没有遗漏即可。数据范围1≤n≤9输入样例4输出样例.Q.. ...Q Q... ..Q. ..Q. Q... ...Q .Q..题解搜索过程按格搜索1.依次遍历每个格子 (x, y)。2.对于当前格子有两种选择不放皇后直接递归到下一个格子 (x, y1)。放皇后如果当前格子所在行、列、两条对角线均无皇后则放置标记占用递归到下一个格子皇后数 1并回溯。3.当处理完所有格子时若已放置的皇后数等于 n则得到一个合法解输出棋盘。答案#include iostream using namespace std; int n; const int N20; char g[N][N]; bool row[N],col[N],dg[N],udg[N];//标记每一行、每一列、主对角线、副对角线是否被占用 void dfs(int x,int y ,int s){//x为行y为列s为当前放置皇后的数量 //当列坐标y到达最右端y n时换到下一行开头 if(yn){ y0; x; } //xn 证明遍历完成 if(xn){ if(sn){//成功放置n个皇后 for(int i0;in;i) { coutg[i]endl; } coutendl; } return; } //当前格子不放皇后直接考虑下一个格子 dfs(x,y1,s); //当前格子放皇后 if(!row[x]!col[y]!dg[xy]!udg[y-xn]){ g[x][y]Q; row[x]col[y]dg[xy]udg[y-xn]true; dfs(x,y1,s1); row[x]col[y]dg[xy]udg[y-xn]false;//回溯 g[x][y].; } } int main(){ cinn; for(int i0;in;i){ for(int j0;jn;j){ g[i][j].; } } dfs(0,0,0); return 0; }要点