n-皇后问题（bfs）

标签：问题 int dg dfs bfs udg 对角线 皇后 col

 

 

 

 

#include<iostream>

using namespace std;

const int N=20;//N*N 两倍

int n;

bool col[N],dg[N],udg[N];//同一列，对角线，反对角线（标记一下是否可以走）

char g[N][N];//记录地图

 

void dfs(int u){//u表示深度

if(u==n){

for(int i=0;i<n;i++)

cout<<g[i]<<endl;//u==n表示已经搜了n行，输出这条路径 i表示y轴

puts("");

return;

}

for(int i=0;i<n;i++){

if(!col[i] && !dg[u+i] && !udg[n-u+i]){//是不在同一列，对角线或者反对角线上的路

g[u][i]='Q';//这条路可以走

col[i]=dg[u+i]=udg[n-u+i]=true;//这条路已经不能走了

dfs(u+1);//遍历下一层

col[i]=dg[u+i]=udg[n-u+i]=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);

}

 

标签：问题,int,dg,dfs,bfs,udg,对角线,皇后,col
From： https://www.cnblogs.com/chenxinyue/p/17216289.html