AcWing 843. n-皇后问题
原题链接
中等
作者:
Diiiiooo_8
,
2024-04-21 16:59:24
,
所有人可见
,
阅读 1
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10;
string q[N][N];
int n;
int check[N];
int st[N]; // 判断数是否使用过
bool isN()
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue; // 排除自己和自己的比较
if (check[i] == check[j] || abs(check[i] - check[j]) == abs(i - j)) return false;
}
}
return true;
}
void printQ() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) cout << q[i][j];
cout << endl;
}
cout << endl;
}
void creatQ() {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (j == check[i]) q[i][j] = "Q";
else q[i][j] = ".";
}
}
void dfs_check(int u)
{
if (u == n) {
if (isN()) {
creatQ();
printQ();
}
return;
}
for (int i = 0; i < n; i++) {
if (!st[i]) {
check[u] = i;
st[i] = 1;
dfs_check(u + 1);
st[i] = 0; // 回溯变回原样
}
}
}
int main()
{
cin >> n;
dfs_check(0);
return 0;
}