P1219 [USACO1.5] 八皇后 Checker Challenge
球球了,帮我看看吧
#include<iostream>
using namespace std;
bool book[30];
bool b_1[30];//x+y
bool b_2[30];//x-y
int n;
long long ans=0;
int now[15];
void dfs(int row){
for(int i=1;i<=n;i++){
if(book[i]==true||b_1[row+i]==true||b_2[i-row]==true)continue;
if(row==n){
ans++;
now[row]=i;
if(ans<=3){
for(int j=1;j<=n;j++)
cout<<now[j]<<" ";
cout<<endl;
}
continue;
}
book[i]=true;b_1[row+i]=true;b_2[i-row]=true;
now[row]=i;
dfs(row+1);
book[i]=false;b_1[row+i]=false;b_2[i-row]=false;
}
return;
}
int main(){
cin>>n;
for(int i=1;i<=29;i++)
{
book[i]=false;
b_1[i]=false;
b_2[i]=false;
}
for(int i=1;i<=n;i++){
book[i]=true;
b_1[i+1]=true;
b_2[i-1]=true;
now[1]=i;
dfs(2);
book[i]=false;
b_1[i+1]=false;
b_2[i-1]=false;
}
cout<<ans;
return 0;
}
//过不了的第一组样例:7
//正确ans:
//1 3 5 7 2 4 6
//1 4 7 3 6 2 5
//1 5 2 6 3 7 4
//40