数据有误
原题链接：122.棋盘问题
2025-01-25 10:36:36
发布于：福建
52阅读
0回复
0点赞
洛谷全AC，ACGOWA2个
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y;
}f[105];
int n,tot,minn=0x3f3f3f3f,a[15][15],r[15][15];
bool vis[105],p[105]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0};
bool check(int x,int y){
if(x>=1){
if(!p[a[x][y]+a[x-1][y]]){
return 0;
}
}
if(y>=1){
if(!p[a[x][y]+a[x][y-1]]){
return 0;
}
}
return 1;
}
void dfs(int step){
if(tot>=minn){
return ;
}
int ln=n*n;
if(step==ln){
if(tot>=minn){
return ;
}
minn=tot;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
r[i][j]=a[i][j];
}
}
return ;
}
int x=f[step].x,y=f[step].y;
for(int i=2;i<=ln;i++){
if(!vis[i]){
//cout<<x<<" "<<y<<" "<<a[x][y]<<endl;
a[x][y]=i;
if(check(x,y)){
if(x==0 || y==0){
tot+=i;
}
vis[i]=1;
dfs(step+1);
vis[i]=0;
if(x==0 || y==0){
tot-=i;
}
}
}
}
}
int main(){
cin>>n;
if(n==1 || n==3){
cout<<"NO";
return 0;
}
for(int i=0;i<n*n;i++){
f[i]={i/n,i%n};
}
tot=1;
a[0][0]=1;
dfs(1);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<r[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
有帮助，赞一个