#27380: 分享我弱弱的扣 (6.3s)


d10831523@gapps.fg.tp.edu.tw (廖與僑)

School : 臺北市立第一女子高級中學
ID : 107948
IP address : [203.64.52.40]
Last Login :
2021-11-25 19:37:58
a160. 祖靈想要下棋!!!!!!!! -- 祖靈的棋魂!!!! | From: [203.64.52.40] | Post Date : 2021-09-29 13:36

#include<bits/stdc++.h>

using namespace std;

#define endl "\n" //酷吧(⁎⁍̴̛ᴗ⁍̴̛⁎)

 

int o[12][12]={0};//output

string xQ="xQ";

int s,n;//s:共幾組解 

bool vi[12]={false},vj[12]={false},ipj[24]={false},imj[24]={false};//紀錄直線斜線有沒有皇后

void dfs(int,int);

 

int main(){

ios::sync_with_stdio(0),cin.tie(0);

while(cin>>n&&n>0){

cout<<endl;

s=0;

dfs(0,n);

cout<<s<<endl;

}

}

 

void dfs(int t,int l){//t:避免重複算 l:還剩幾個皇后要放

if(l==0){

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

for(int j=0;j<n;j++)cout<<xQ[o[i][j]];cout<<endl;

}

cout<<endl;

s++;return;

}

for(int x=t;x<n*n;x++){

int i=x/n,j=x%n;

if(!vi[i])if(!vj[j])if(!ipj[i+j]&&!imj[n+i-j]){

vi[i]=true,vj[j]=true,ipj[i+j]=true,imj[n+i-j]=true;

o[i][j]=1;

dfs(x,l-1);

vi[i]=false,vj[j]=false,ipj[i+j]=false,imj[n+i-j]=false;

o[i][j]=0;

}

}

}

 
ZeroJudge Forum