AcWing 843. n-皇后问题 三种方法求解
原题链接
中等
作者:
辉小歌
,
2021-05-09 14:41:16
,
所有人可见
,
阅读 327
STL大法 54 ms
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[15]={1,2,3,4,5,6,7,8,9,10};
bool b[15][15];
int main(void)
{
int n; cin>>n;
do
{
bool flag=true;
memset(b,0,sizeof b);
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(abs(i-j)==abs(a[i]-a[j]))
{
flag=false;
break;
}
}
if(!flag)break;
}
if(flag)
{
for(int i=1;i<=n;i++) b[a[i-1]][i]=true;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(b[i][j]) cout<<"Q";
else cout<<".";
}
cout<<endl;
}
cout<<endl;
}
}while(next_permutation(a,a+n));
return 0;
}
dfs 暴力枚举 71 ms
#include<cstdio>
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
int n;
int path[15];
bool vis[15];
void dfs(int index)
{
if(index==n)
{
bool flag=true;
bool b[15][15]={0};
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(abs(i-j)==abs(path[i]-path[j]))
{
flag=false;
break;
}
}
if(!flag) break;
}
if(flag)
{
for(int i=1;i<=n;i++) b[path[i-1]][i]=true;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(b[i][j]) cout<<"Q";
else cout<<".";
}
cout<<endl;
}
cout<<endl;
}
return;
}
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
path[index]=i;
vis[i]=true;
dfs(index+1);
vis[i]=false;
}
}
}
int main(void)
{
cin>>n;
dfs(0);
return 0;
}
dfs+ 剪枝 23 ms
#include<cstdio>
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
int n;
int path[15];
bool vis[15];
void dfs(int index)
{
for(int i=0;i<index;i++)
for(int j=i+1;j<index;j++)
if(abs(i-j)==abs(path[i]-path[j])) return;
if(index==n)
{
bool b[15][15]={0};
for(int i=1;i<=n;i++) b[path[i-1]][i]=true;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(b[i][j]) cout<<"Q";
else cout<<".";
}
cout<<endl;
}
cout<<endl;
return;
}
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
path[index]=i;
vis[i]=true;
dfs(index+1);
vis[i]=false;
}
}
}
int main(void)
{
cin>>n;
dfs(0);
return 0;
}