东莞市建设安监监督网站首页多米诺网站建设服务
题目描述
给出一个n×nn\times nn×n的国际象棋棋盘，你需要在棋盘中摆放nnn个皇后，使得任意两个皇后之间不能互相攻击。具体来说，不能存在两个皇后位于同一行、同一列，或者同一对角线。请问共有多少种摆放方式满足条件。
输入描述:
一行，一个整数n(1≤n≤12)n(1\le n \le 12)n(1≤n≤12)，表示棋盘的大小。
输出描述:
输出一行一个整数，表示总共有多少种摆放皇后的方案，使得它们两两不能互相攻击。
示例1
输入
4
输出
2
想法：
就按题意，一个格子一个格子枚举，并看一下有没有行冲突，列冲突，对角线冲突，但结果答案是错的。
代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int ans=0;
int a[15][15];
int st[15][15];
int r[15];//行冲突
int c[15];//列冲突
int djx[2];//对角线冲突
void dfs(int gs){//摆了的皇后个数
//st[x][y]=1;
if(gs>n){
ans++;
return ;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
//if(st[i][j]) break;
if(r[i]) break;
if(c[j]) continue;
if(djx[0]&&i==j) continue;
if(djx[1]&&i+j==n+1) continue;
r[i]=1;
c[j]=1;
if(i==j){
djx[0]=1;
dfs(gs+1);
djx[0]=0;
}
else if(i+j==n+1){
djx[1]=1;
dfs(gs+1);
djx[1]=0;
}
else dfs(gs+1);
r[i]=0;
c[j]=0;
}
}
}
int main(){
cin>>n;
dfs(0);
cout<<ans;
}
网课：
看了网课后，发现还是有点问题的吧。首先，对角线冲突理解错了，题目指的是每条对角线，而我以为是主对角线和副对角线两条。然后我又想了下怎么标记对角线，找了下对角线的下标有什么规律，emm但也还是想不到怎么表示。网课的提供了两种方法，一种是直接将所有对角线标序号，然后弄个标记数组；第二种就是看规律，主对角线方向上的位于同一条对角线的坐标i+j都是同一个值，副对角线方向上的位于同一条对角线的坐标i-j都是同一个值。利用这点，可以弄两个标记数组。但还有问题，就是副对角线方向上的某些对角线坐标相减是负的，需要把数组下标平移一下。我找规律的时候也有注意到一点点吧，但没那么深刻。还有一点，就是网课的方法搜索时是一行一行搜的，每一行放一个皇后，看是否满足条件，这样直接不用考虑行冲突了。我是一格一格搜索的，复杂度更高。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n;
int ans=0;
int c[N];
int fdjx[N+N-1+N];//平移
int zdjx[N+N-1];
void dfs(int r){//行
if(r>n){
ans++;
return ;
}
for(int i=1;i<=n;i++){//列
if(c[i]) continue;
if(fdjx[r-i+n]) continue;
if(zdjx[r+i]) continue;
c[i]=1;
fdjx[r-i+n]=1;
zdjx[r+i]=1;
dfs(r+1);
c[i]=0;
fdjx[r-i+n]=0;
zdjx[r+i]=0;
}
}
int main(){
cin>>n;
dfs(1);
cout<<ans;
}
修改：
但是吧，我现在按我的想法写，就是一格一格搜索，还是弄不出来。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n;
int ans=0;
int c[N];
int r[N];
int fdjx[N+N-1+N];//平移
int zdjx[N+N-1];
void dfs(int gs){//行
if(gs>n){
ans++;
return ;
}
for(int i=1;i<=n;i++){//列
for(int j=1;j<=n;j++){
if(c[j]) continue;
if(r[i]) break;
if(fdjx[i-j+n]) continue;
if(zdjx[i+j]) continue;
c[j]=1;
r[i]=1;
fdjx[i-j+n]=1;
zdjx[j+i]=1;
dfs(gs+1);
c[i]=0;
r[i]=0;
fdjx[i-j+n]=0;
zdjx[j+i]=0;
}
}
}
int main(){
cin>>n;
dfs(1);
cout<<ans;
}