当前位置:网站首页>acwing 843. N-queen problem
acwing 843. N-queen problem
2022-07-07 04:38:00 【_ Liu Xiaoyu】
n− The Queen's problem means that n Put a queen in n×n On my chess board , So that the queen can't attack each other , That is, no two Queens can be in the same line 、 On the same column or slash .
Now, given an integer n, Please output all the pieces that meet the conditions .
Input format
All in one line , Contains integers n.
Output format
Each solution accounts for n That's ok , Each line outputs a length of n String , Used to represent the complete chessboard state .
among . Indicates that the grid status of a position is empty ,Q The queen is placed on the square indicating a certain position .
After the output of each scheme is completed , Output a blank line .
Be careful : There must be no extra spaces at the end of the line .
The order of output schemes is arbitrary , As long as there is no repetition and no omission .
Data range
1≤n≤9
sample input :
4
sample output :
.Q…
…Q
Q…
…Q.
…Q.
Q…
…Q
.Q…
This question is also DFS, It can be arranged according to
solution 1: Enumerate by row ( It's also the same question Full Permutation Allied )
It can be remembered as a template
#include <iostream>
using namespace std;
const int N = 20;
// bool Array is used to determine whether the next location of the search is feasible
// col Column ,dg Diagonals ,udg Anti diagonal
// g[N][N] Used to save path
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
void dfs(int u) {
// u == n It means that we have searched n That's ok , So output this path
if (u == n) {
for (int i = 0; i < n; i ++ ) puts(g[i]); // Equivalent to cout << g[i] << endl;
puts(""); // Line break
return;
}
// enumeration u This business , Search for legal Columns , // Here, we can regard line as y, Column as x
// Here is the enumeration number u That's ok , The first i Column , Whether to release the queen , u= y, i = x after ===》 The diagonal is u + i、u - i + n
for (int i = 0; i < n; i ++ )
// prune ( For points that do not meet the requirements , No more searching )
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] = '.'; // Restore the scene
}
}
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;
}
Method 2: Enumerate according to each element
Every position has 2 In this case , Put it or not , There is... In all n2
Time complexity : O(2 Of n2 Power ), I can't fight it out , Forgive me
Schematic diagram : Draw like this
Ideas : Search step by step according to each position .
code:
// Different search order Time complexity is different So the search order is very important !
#include <iostream>
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N]; // Because it's a search , So I added row
// s Indicates the number of queens that have been put on
void dfs(int x, int y, int s)
{
// Deal with situations beyond the boundary , Whether to put this directly in one line or not , After walking , Jump to the next line to start
if (y == n) y = 0, x ++ ;
if (x == n) {
// x==n Description has been enumerated n^2 It's a place
if (s == n) {
// s==n It means that it was successfully put on n A queen
for (int i = 0; i < n; i ++ ) puts(g[i]);
puts("");
}
return;
}
// Branch 1: Put the queen
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] = '.';
}
// Branch 2: Don't let the queen go
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;
}
边栏推荐
- DFS和BFS概念及实践+acwing 842 排列数字(dfs) +acwing 844. 走迷宫(bfs)
- A series of shortcut keys for jetbrain pychar
- 一度辍学的数学差生,获得今年菲尔兹奖
- mpf2_ Linear programming_ CAPM_ sharpe_ Arbitrage Pricin_ Inversion Gauss Jordan_ Statsmodel_ Pulp_ pLU_ Cholesky_ QR_ Jacobi
- Mathematical analysis_ Notes_ Chapter 10: integral with parameters
- Formation continue en robotique (automatisation) - 2022 -
- Kotlin compose text supports two colors
- EasyUI export excel cannot download the method that the box pops up
- Why does WordPress open so slowly?
- 接口自动化测试实践指导(中):接口测试场景有哪些
猜你喜欢
Why does WordPress open so slowly?
The easycvr platform is connected to the RTMP protocol, and the interface call prompts how to solve the error of obtaining video recording?
mpf2_线性规划_CAPM_sharpe_Arbitrage Pricin_Inversion Gauss Jordan_Statsmodel_Pulp_pLU_Cholesky_QR_Jacobi
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
[multi threading exercise] write a multi threading example of the producer consumer model.
DFS和BFS概念及实践+acwing 842 排列数字(dfs) +acwing 844. 走迷宫(bfs)
1.19.11. SQL client, start SQL client, execute SQL query, environment configuration file, restart policy, user-defined functions, constructor parameters
EasyCVR集群版本添加RTSP设备提示服务器ID错误,该如何解决?
程序员上班摸鱼,这么玩才高端!
[system management] clear the icon cache of deleted programs in the taskbar
随机推荐
Win11图片打不开怎么办?Win11无法打开图片的修复方法
機器人(自動化)課程的持續學習-2022-
A picture to understand! Why did the school teach you coding but still not
Digital chemical plant management system based on Virtual Simulation Technology
Gpt-3 is a peer review online when it has been submitted for its own research
What if the win11 screenshot key cannot be used? Solution to the failure of win11 screenshot key
AI表现越差,获得奖金越高?纽约大学博士拿出百万重金,悬赏让大模型表现差劲的任务
案例大赏:英特尔携众多合作伙伴推动多领域AI产业创新发展
两个div在同一行,两个div不换行「建议收藏」
掌握软件安全测试方法秘笈,安全测试报告信手捏来
什么是Web3
True global ventures' newly established $146million follow-up fund was closed, of which the general partner subscribed $62million to invest in Web3 winners in the later stage
leetcode 53. Maximum subarray maximum subarray sum (medium)
What about the collapse of win11 playing pubg? Solution to win11 Jedi survival crash
Different meat customers joined hands with Dexter to launch different hamburgers in some stores across the country
Data security -- 12 -- Analysis of privacy protection
架构实战训练营|课后作业|模块 6
NFT meta universe chain diversified ecosystem development case
Surpassing postman, the new generation of domestic debugging tool apifox is elegant enough to use
On the 110th anniversary of Turing's birth, has the prediction of intelligent machine come true?