非常有意思的一道题

原题链接：36246.棋盘问题

不想AC

2025-01-04 17:46:20

发布于：福建

10阅读

0回复

0点赞

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
}f[105];
int n,ln,minn=0x3f3f3f3f,a[10][10];
bool 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};
bitset<55>vis;
bool check(int x,int y){
    if(x>=1 && !p[a[x][y]+a[x-1][y]]){
        return 0;
    }
    if(y>=1 && !p[a[x][y]+a[x][y-1]]){
        return 0;
    }
    return 1;
}
void dfs(int step,int tot){
    if(tot>=minn){
        return ;
    }
    if(step==ln){
        minn=tot;
        return ;
    }
    int x=f[step].x,y=f[step].y;
    for(int i=2;i<=ln;i++){
        if(!vis[i]){
            a[x][y]=i;
            if(check(x,y)){
                vis[i]=1;
                if(step<2*n-1){
                    dfs(step+1,tot+i);
                }else{
                    dfs(step+1,tot);
                }
                vis[i]=0;
            }
        }
    }
}
int main(){
    cin>>n;
    if(n==1 || n==3){
        cout<<"NO";
        return 0;
    }
    ln=n*n;
    for(int i=0;i<n;i++){
        f[i]={0,i};
    }
    for(int i=n;i<2*n-1;i++){
        f[i]={i-n+1,0};
    }
    for(int i=2*n-1;i<ln;i++){
        f[i]={1+(i-2*n+1)%(n-1),1+(i-2*n+1)/(n-1)};
    }
    a[0][0]=1;
    dfs(1,1);
    cout<<minn;
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论