dfs的时间复杂度可以理解为:首先是指数级的,设b是搜索树的最大分支因子,m是搜索树的最大深度,那么时间复杂度为O(b^m)
搜索顺序为一行一行
#include<iostream>
using namespace std;
const int N=20;
int n,idx;
char g[N][N]; //n-皇后棋盘
bool col[N],dg[N],udg[N]; //列,对角线,反对角线
//u已经能保证不在同一行了,每次都往下一层搜素,深搜
void dfs(int u){
if(u==n){
printf("第%d种解:\n",++idx);
for(int i=0;i<n;i++) puts(g[i]);
puts("");
return ;
}
for(int i=0;i<n;i++){
if(!col[i]&&!dg[i-u+n]&&!udg[u+i]){
g[u][i]='Q';
col[i]=dg[i-u+n]=udg[u+i]=true;
dfs(u+1);
g[u][i]='#';
col[i]=dg[i-u+n]=udg[u+i]=false;
}
}
}
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;
}
搜索顺序为一格一格
#include<iostream>
using namespace std;
const int N=20;
int n;
char g[N][N];//存棋盘,初始化为'#'
bool row[N],col[N],dg[N],udg[N];//行,列,对角线,反对角线
void dfs(int x,int y,int sum){
if(y==n) y=0,x++;
if(x==n){
if(sum==n){
for(int i=0;i<n;i++) puts(g[i]);
puts("");
}
return ;
}
//不放,dfs下一个格子
dfs(x,y+1,sum);
//放
if(!row[x]&&!col[y]&&!dg[x-y+n]&&!udg[x+y]){
g[x][y]='Q';
row[x]=col[y]=dg[x-y+n]=udg[x+y]=true;
dfs(x,y+1,sum+1);
g[x][y]='#';
row[x]=col[y]=dg[x-y+n]=udg[x+y]=false;
}
}
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;
}
洛谷的n-皇后(稍稍不同)
https://www.luogu.com.cn/problem/P1219
方法一
一格一格搜,会超时, 首先我们dfs本身就是爆搜,时间复杂度就不低,时间复杂度为 O(2^(n*n))
#include<ostream>
#include<vector>
using namespace std;
const int N=20;
int n,res=0;
vector<int> queen;
bool row[N],col[N],dg[N],udg[N];
void dfs(int x,int y,int sum){
if(y==n) y=0,x++;
if(x==n){
if(sum==n){
res++;
if(res<=3){
for(auto i:queen) printf("%d ",i);
puts("");
}
}
return ;
}
//先写放,再写不放,因为题目要求是按字典序输出,也就是顺序,否则先写不放再写放,会倒序输出
if(!row[x]&&!col[y]&&!dg[x-y+n]&&!udg[x+y]){
queen.push_back(y+1);
row[x]=col[y]=dg[x-y+n]=udg[x+y]=true;
dfs(x,y+1,sum+1);
queen.pop_back();
row[x]=col[y]=dg[x-y+n]=udg[x+y]=false;
}
dfs(x,y+1,sum);
}
int main(){
scanf("%d",&n);
dfs(0,0,0);
printf("%d",res);
return 0;
}
方法二
一行一行搜,AC,时间复杂度为 O(n^n),最差为O(n*n!)
#include<iostream>
#include<vector>
using namespace std;
const int N=20;
int n,idx;
vector<int> queen;
bool col[N],dg[N],udg[N]; //列,对角线,反对角线
//u已经能保证不在同一行了,每次都往下一层搜素,深搜
void dfs(int u){
if(u==n){
idx++;
if(idx<=3){
for(auto i:queen) printf("%d ",i);
puts("");
}
return ;
}
for(int i=0;i<n;i++){
if(!col[i]&&!dg[i-u+n]&&!udg[u+i]){
queen.push_back(i+1);
col[i]=dg[i-u+n]=udg[u+i]=true;
dfs(u+1);
queen.pop_back();
col[i]=dg[i-u+n]=udg[u+i]=false;
}
}
}
int main(){
scanf("%d",&n);
dfs(0);
printf("%d",idx);
return 0;
}