AcWing 843. n-皇后问题(朴素dfs)
原题链接
中等
作者:
快速冥
,
2024-01-09 19:15:06
,
所有人可见
,
阅读 42
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 10;
char path[N][N];
int n;
bool check(int u,int j){
//由于是一行一行往下填,所以只用检测当前行的上方
//检测正上方
for(int i = 0; i < u; ++i){
if(path[i][j] == 'Q') return false;
}
//检测左斜线
int x = u - 1,y = j - 1;
while(x >= 0 && y >= 0){
if(path[x][y] == 'Q') return false;
--x;
--y;
}
//检测右斜线
x = u - 1,y = j + 1;
while(x >= 0 && y < n){
if(path[x][y] == 'Q') return false;
--x;
++y;
}
return true;
}
void dfs(int u){
//填完n行,是时候输出了
if(u == n){
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j)
printf("%c",path[i][j]);
puts("");
}
puts("");
return;
}
for(int j = 0; j < n; ++j){
//满足条件才可以进行dfs
if(check(u,j)){
//满足条件,填下当前行的皇后位置
path[u][j] = 'Q';
//填下一行
dfs(u + 1);
//回溯恢复初始状态,探索下一列
path[u][j] = '.';
}
}
}
int main(){
scanf("%d",&n);
memset(path,'.',sizeof path);
dfs(0);
return 0;
}
开心~第一道在acwing自己写出来的中等题