当前位置:网站首页>acwing 843. n-皇后问题
acwing 843. n-皇后问题
2022-07-06 22:04:00 【_刘小雨】
n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 n,请你输出所有的满足条件的棋子摆法。
输入格式
共一行,包含整数 n。
输出格式
每个解决方案占 n 行,每行输出一个长度为 n 的字符串,用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空,Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后,输出一个空行。
注意:行末不能有多余空格。
输出方案的顺序任意,只要不重复且没有遗漏即可。
数据范围
1≤n≤9
输入样例:
4
输出样例:
.Q…
…Q
Q…
…Q.
…Q.
Q…
…Q
.Q…
这题也是DFS, 可以根据全排列的
解法1:按行枚举 (也是跟上一题 全排列类似的)
可以作为模版进行记忆
#include <iostream>
using namespace std;
const int N = 20;
// bool数组用来判断搜索的下一个位置是否可行
// col列,dg对角线,udg反对角线
// g[N][N]用来存路径
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
void dfs(int u) {
// u == n 表示已经搜了n行,故输出这条路径
if (u == n) {
for (int i = 0; i < n; i ++ ) puts(g[i]); // 等价于cout << g[i] << endl;
puts(""); // 换行
return;
}
// 枚举u这一行,搜索合法的列, // 这里可将行看成y, 列看成x
// 这里是枚举第u行, 第i 列, 是否放皇后, u= y, i = x 后 ===》 对角线就是 u + i、u - i + n
for (int i = 0; i < n; i ++ )
// 剪枝(对于不满足要求的点,不再继续往下搜索)
if (!col[i] && !dg[u + i] && !udg[n - i + u])
{
g[u][i] = 'Q';
col[i] = dg[u + i] = udg[n - i + u] = true;
dfs(u + 1);
col[i] = dg[u + i] = udg[n - i + u] = false;
g[u][i] = '.'; // 恢复现场
}
}
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;
}
方法2: 按照每个元素进行枚举
每个位置都有2种情况,放还是不放,总共就有n2
时间复杂度: O(2的n2次方), 打不出来了,见谅
原理图: 就类似这样画下去
思路: 按照每个位置放不放的步骤一点一点进行搜索。
code:
// 不同搜索顺序 时间复杂度不同 所以搜索顺序很重要!
#include <iostream>
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N]; // 因为是一个个搜索,所以加了row
// s表示已经放上去的皇后个数
void dfs(int x, int y, int s)
{
// 处理超出边界的情况, 这个是直接一行进行放还是不放, 一行走完了,跳到下一行开始
if (y == n) y = 0, x ++ ;
if (x == n) {
// x==n说明已经枚举完n^2个位置了
if (s == n) {
// s==n说明成功放上去了n个皇后
for (int i = 0; i < n; i ++ ) puts(g[i]);
puts("");
}
return;
}
// 分支1:放皇后
if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
g[x][y] = 'Q';
row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
dfs(x, y + 1, s + 1);
row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
g[x][y] = '.';
}
// 分支2:不放皇后
dfs(x, y + 1, s);
}
int main() {
cin >> n;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
g[i][j] = '.';
dfs(0, 0, 0);
return 0;
}
边栏推荐
- EasyCVR无法使用WebRTC进行播放,该如何解决?
- 5年自动化测试,终于进字节跳动了,年薪30w其实也并非触不可及
- Gpt-3 is a peer review online when it has been submitted for its own research
- [knife-4j quickly build swagger]
- POJ training plan 2253_ Frogger (shortest /floyd)
- 【自动化经验谈】自动化测试成长之路
- Up to 5million per person per year! Choose people instead of projects, focus on basic scientific research, and scientists dominate the "new cornerstone" funded by Tencent to start the application
- Break the memory wall with CPU scheme? Learn from PayPal to expand the capacity of aoteng, and the volume of missed fraud transactions can be reduced to 1/30
- 【线段树实战】最近的请求次数 + 区域和检索 - 数组可修改+我的日程安排表Ⅰ/Ⅲ
- 论文上岸攻略 | 如何快速入门学术论文写作
猜你喜欢
The root file system of buildreoot prompts "depmod:applt not found"
【ArcGIS教程】专题图制作-人口密度分布图——人口密度分析
buildroot的根文件系统提示“depmod:applt not found”
见到小叶栀子
【实践出真理】import和require的引入方式真的和网上说的一样吗
【线段树实战】最近的请求次数 + 区域和检索 - 数组可修改+我的日程安排表Ⅰ/Ⅲ
5年自动化测试,终于进字节跳动了,年薪30w其实也并非触不可及
How to open win11 remote desktop connection? Five methods of win11 Remote Desktop Connection
C # use Siemens S7 protocol to read and write PLC DB block
数学分析_笔记_第10章:含参变量积分
随机推荐
Up to 5million per person per year! Choose people instead of projects, focus on basic scientific research, and scientists dominate the "new cornerstone" funded by Tencent to start the application
5年自动化测试,终于进字节跳动了,年薪30w其实也并非触不可及
Lecture 3 of "prime mover x cloud native positive sounding, cost reduction and efficiency enhancement lecture" - kubernetes cluster utilization improvement practice
Unit test asp Net MVC 4 Application - unit testing asp Net MVC 4 apps thoroughly
POJ training plan 2253_ Frogger (shortest /floyd)
每人每年最高500万经费!选人不选项目,专注基础科研,科学家主导腾讯出资的「新基石」启动申报
The easycvr platform is connected to the RTMP protocol, and the interface call prompts how to solve the error of obtaining video recording?
EasyCVR集群重启导致其他服务器设备通道状态离线情况的优化
Have you got the same "artifact" of cross architecture development praised by various industry leaders?
[system management] clear the icon cache of deleted programs in the taskbar
深耕开发者生态,加速AI产业创新发展 英特尔携众多合作伙伴共聚
The most complete security certification of mongodb in history
C#使用西门子S7 协议读写PLC DB块
leetcode 53. Maximum Subarray 最大子数组和(中等)
B站大佬用我的世界搞出卷积神经网络,LeCun转发!爆肝6个月,播放破百万
Golang calculates constellations and signs based on birthdays
Deeply cultivate the developer ecosystem, accelerate the innovation and development of AI industry, and Intel brings many partners together
EasyUI export excel cannot download the method that the box pops up
The worse the AI performance, the higher the bonus? Doctor of New York University offered a reward for the task of making the big model perform poorly
Fix the problem that the highlight effect of the main menu disappears when the easycvr Video Square is clicked and played