网站布局的好坏的几个要素,Wordpress如何调用搜索框,steam交易链接是什么,做网站什么码n−皇后问题是指将 n 个皇后放在 nn 的国际象棋棋盘上#xff0c;使得皇后不能相互攻击到#xff0c;即任意两个皇后都不能处于同一行、同一列或同一斜线上。 现在给定整数 n#xff0c;请你输出所有的满足条件的棋子摆法。
输入格式
共一行#xff0c;包含整数 n。
输出…n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上使得皇后不能相互攻击到即任意两个皇后都不能处于同一行、同一列或同一斜线上。 现在给定整数 n请你输出所有的满足条件的棋子摆法。
输入格式
共一行包含整数 n。
输出格式
每个解决方案占 n行每行输出一个长度为 n的字符串用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后输出一个空行。
注意行末不能有多余空格。
输出方案的顺序任意只要不重复且没有遗漏即可。
数据范围
1≤n≤9
输入样例
4输出样例
.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q..解题思路
每次遍历每个格子有两种选择放Q不放Q。
如果放Q需要检查当前行列对角线反对角线是否已被标记过。
对角线与反对角线表示由于直线方程斜率正负有两种表达yxb,y-xb;
正好对应着对角线与反对角线不过在途中x为行y为列需要互换一下。
参考代码
#include iostream
#include cstring
#include algorithmusing namespace std;
const int N 10;
char g[N][N];
bool row[N],col[N],dg[N],udg[N];//行列正对角线xy反对角线(n-yx)
bool st[N];
int n;void dfs(int u,int x,int y)
{if(un) return;if(yn) y 0,x;if(xn){if(un){for(int i0;in;i) puts(g[i]);puts( );}return;}g[x][y] .;dfs(u,x,y1);if(!row[x] !col[y] !dg[xy] !udg[n-yx]){g[x][y] Q;row[x] col[y] dg[xy] udg[n-yx] true;dfs(u1,x,y1);g[x][y] .;row[x] col[y] dg[xy] udg[n-yx] false;}
}int main()
{cinn;dfs(0,0,0);return 0;
}
