题目描述:
一个如下的6×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
请输出前 3 个解。最后一行是解的总个数。
#include<iostream>
using namespace std;
int n;
int ans[15][2];
int dir[4][2]={-1,0,0,1,1,0,0,-1};
int count,sum;
void dfs(int a=1,int b=1){
for(int i=1;i<=count;i++){
if(a==ans[i][0]||b==ans[i][1])
return;
int k=1.0*(ans[i][1]-b)/(ans[i][0]-a);
if(k==1||k==-1)
return;
}
count++;
ans[count][0]=a;
ans[count][1]=b;
if(count==n){
for(int i=1;i<=n;i++)
cout<<ans[i][1]<<" ";
sum++;
return;
}
for(int i=0;i<4;i++){
a+=dir[i][0];
b+=dir[i][1];
if(a>=1&&a<=n&&b>=1&&b<=n){
dfs(a,b);
a-=dir[i][0];
b-=dir[i][1];
}
}
}
int main(){
cin>>n;
dfs();
cout<<sum;
return 0;
}
参考下这个代码:
#include<iostream>
#include<cstdio>
#include<vector>
#define N 40
using namespace std;
bool vis[N]={0};
bool vt[2][N]={0};
int n=0;
int p=13;
int ret=0;
vector<int> ans;
void dfs(int x){
if(x==n+1){
ret++;
if(ret<=3){
for(int i=0;i<ans.size();i++){
if(i==0) printf("%d",ans[i]);
else printf(" %d",ans[i]);
}
printf("\n");
}
}
for(int y=1;y<=n;y++){
if(!vis[y]&&!vt[1][x+y]&&!vt[0][x-y+13]){
vis[y]=vt[1][x+y]=vt[0][x-y+p]=1;
ans.push_back(y);
dfs(x+1);
ans.pop_back();
vis[y]=vt[1][x+y]=vt[0][x-y+p]=0;
}
}
}
int main(){
cin>>n;
dfs(1);
printf("%d\n",ret);
return 0;
}
如有帮助,望采纳!谢谢!