2n皇后
作者:
桑榆晚
,
2023-03-10 06:31:07
,
所有人可见
,
阅读 108
#include<iostream>
using namespace std;
const int N=20;
char g[N][N];
char G[N][N];
bool col[N],dg[N],udg[N];
bool col2[N],dg2[N],udg2[N];
int n,num=0;
void white(int u){
if(u==n){
num++;
return;
}
for(int i=0;i<n;i++){
if(!col2[i]&&!dg2[i+u]&&!udg2[u-i+n]&&G[u][i]=='1'){
G[u][i]='0';
col2[i]=dg2[i+u]=udg2[u-i+n]=true;
white(u + 1);
col2[i]=dg2[i+u]=udg2[u-i+n]=false;
G[u][i]='1';
}
}
}
void black(int u){
if(u==n){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
G[i][j]=g[i][j];
white(0);
return;
}
for(int i=0;i<n;i++){
if(!col[i]&&!dg[i+u]&&!udg[u-i+n]&&g[u][i]=='1'){
g[u][i]='0';
col[i]=dg[i+u]=udg[u-i+n]=true;
black(u + 1);
col[i]=dg[i+u]=udg[u-i+n]=false;
g[u][i]='1';
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>g[i][j];
black(0);
cout<<num;
return 0;
}
6
👻