如何做国际网站首页,电子商务系统网站建设,环保网站建设方案,wordpress 设置图片大小n−n−皇后问题是指将 nn 个皇后放在 nnnn 的国际象棋棋盘上#xff0c;使得皇后不能相互攻击到#xff0c;即任意两个皇后都不能处于同一行、同一列或同一斜线上。 现在给定整数 nn#xff0c;请你输出所有的满足条件的棋子摆法。
输入格式
共一行#xff0c;包含整数 n…n−n−皇后问题是指将 nn 个皇后放在 n×nn×n 的国际象棋棋盘上使得皇后不能相互攻击到即任意两个皇后都不能处于同一行、同一列或同一斜线上。 现在给定整数 nn请你输出所有的满足条件的棋子摆法。
输入格式
共一行包含整数 nn。
输出格式
每个解决方案占 nn 行每行输出一个长度为 nn 的字符串用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后输出一个空行。
注意行末不能有多余空格。
输出方案的顺序任意只要不重复且没有遗漏即可。
数据范围
1≤n≤91≤n≤9
输入样例
4输出样例
.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q..思路
深度优先搜索我们需要排除永远不可能的情况剪枝首先是初始化二维数组把二维数组初始化为. for(int i0;in;i){for(int j0;jn;j){g[i][j].;}}
深度优先搜索分两步走第一步是判断有没有走到终点走到终点就输出我们需要的答案 if(un){for(int i0;in;i) puts(g[i]);puts();return;}
第二步是遍历每一行利用条件判断找到可以符合条件的情况该题是行对角线反对角线不能被使用过然后改变使用状态修改字符数组的内容递归调用dfs函数恢复现场把状态和字符数组的内容都修改回来 int xu;for(int y0;yn;y){if(!col[y]!dg[yx]!udg[y-xn]){col[y]dg[yx]udg[y-xn]true;g[x][y]Q;dfs(x1);col[y]dg[yx]udg[y-xn]false;g[x][y].;}}
这里把u和i更换成了x和y感觉更加方便理解
代码
#includebits/stdc.h
using namespace std;int n;
const int N20;
char g[N][N];
bool col[N],dg[N],udg[N];void dfs(int u)
{if(un){for(int i0;in;i) puts(g[i]);puts();return;}int xu;for(int y0;yn;y){if(!col[y]!dg[yx]!udg[y-xn]){col[y]dg[yx]udg[y-xn]true;g[x][y]Q;dfs(x1);col[y]dg[yx]udg[y-xn]false;g[x][y].;}}
}int main()
{scanf(%d,n);for(int i0;in;i){for(int j0;jn;j){g[i][j].;}}dfs(0);return 0;
}
