当前位置:网站首页>Eight queens n Queens
Eight queens n Queens
2022-07-27 00:29:00 【Deep dream, high ambition, floating life like a dream】

Refer to the correspondents playing the Blue Bridge Cup If you invade or delete
All codes are similar to those of the original blogger I feel that the array is set too much, and I want to change the code
Wrote a set At first, the function simply thought Set each array element to 0 1 that will do I found something wrong after running Later, it was found that the array elements can be set +=x As long as it is in the same row or diagonal line +1 If multiple conditions are met, it will increase Only when The array element is 0 by 0 It will be considered as the place where the queen can be placed
#include <iostream>
using namespace std;
int map[11][11];
int a[10]; // a[] Store solution
int n; // Chessboard size
int ans;
bool check(int i, int j) // Check (i,j) Is it legal
{
if (!map[i][j])
return true; // b[j],c[i-j+n],d[i+j] by 0 This indicates that this point can be used to place chess pieces .
return false;
}
void set(int i, int j, int x)
{
for (int z = 1; z <= n; z++)
{
map[z][j] += x;
map[i][z] += x;
}
for (int z = 1; z <= n; z++)
{
if (i + z <= n && j + z <= n)
{
map[i + z][j + z] += x;
}
if (i + z <= n && j - z >= 1)
{
map[i + z][j - z] += x;
}
if (i - z >= 1 && j + z <= n)
{
map[i - z][j + z] += x;
}
if (i - z >= 1 && j - z >= 1)
{
map[i - z][j - z] += x;
}
}
}
void dfs(int i) // dfs The first i Row chess pieces
{
// The boundary conditions
if (i > n) // dfs Finish all the pieces
{
;
ans++;
if (ans <= 3) // Just the first three solutions
{
for (int i = 1; i <= n; i++) // Output solution
{
cout << a[i] << ' ';
}
cout << endl;
}
return;
}
for (int j = 1; j <= n; j++) // Enumerate all positions of a row
{
//(i,j) Points meet the conditions for putting chess pieces , Let's put the pieces on (i,j) spot
if (check(i, j))
{
a[i] = j; // The column number satisfying the solution exists a[i] in
set(i, j, 1);
dfs(i + 1); // Handle the pieces in the next line
set(i, j, -1);
}
}
}
int main()
{
cin >> n;
dfs(1);
cout << ans << endl;
return 0;
}
边栏推荐
- Matlab simulation of inverted pendulum control system based on qlearning reinforcement learning
- MySql
- LeetCode题目——二叉树篇
- 放图仓库-3(功能图像)
- Resolve Microsoft 365 and Visio conflicts
- Comparative simulation of LEACH protocol performance, including the number of dead nodes, data transmission, network energy consumption, the number of cluster heads and load balance
- Leetcode - hash table
- CSDN文章语法规则
- Leetcode high frequency question: the choice of the inn, how many options to choose accommodation, to ensure that you can find a coffee shop with a minimum consumption of no more than p yuan in the ev
- Machine learning model -- lightgbm
猜你喜欢

Database: MySQL foundation +crud basic operation

放图仓库-2(函数图像)

Arcgis和Cass实现断面展高程点

Double. isNaN(double var)

Shang school software testing (1) software testing curriculum system, advantages, learning suggestions, understanding software, software testing and defects, software testing process, debugging and te

LeetCode题目——数组篇

7_主成分分析法(Principal Component Analysis)
![[PCB open source sharing] stc32g12k128/stc8h8k64u development board](/img/f1/48b344722820ab262e751aebf65411.png)
[PCB open source sharing] stc32g12k128/stc8h8k64u development board

画冲击函数

Viterbi Viterbi decoding bit error rate simulation, modulation is QPSK, channel is Gaussian white noise
随机推荐
Web middleware log analysis script 1.0 (shell script)
12_决策树(Decision tree)
Anaconda = > pycharm=> CUDA=> cudnn=> pytorch environment configuration
3_Jupyter Notebook, numpy和matplotlib
7_ Principal component analysis
C and pointer Chapter 18 runtime environment 18.7 problems
c语言 比大小的多种描述,不要只拘泥于一种写法
[Qt]解决中文乱码问题
Matlab based medical imaging technology filtering backprojection simulation, including direct backprojection, S-L filtering, R-L filtering, LeWitt filtering
CSDN article syntax rules
Oracle data guard service, process and protection mode
Machine learning model -- lightgbm
MySql
【2. Tmux 操作】
Knowledge distillation -- pytorch implementation
Signal and system impulse response and step response
Fourier analysis (basic introduction)
C语言 求素数、闰年以及最小公倍数最大公约数
Three tier architecture simulation
CCPD data set processing (target detection and text recognition)