90求调,TLE两个点
查看原帖
90求调,TLE两个点
1512627
CQBZqc楼主2025/7/1 20:56
#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;

int T;
int a[10][10];
bool ha[10][10],li[10][10],go[10][10];
struct node{
    int val;
    PII id;
}srt[100];

inline bool cmp(node x,node y) {
    return x.val<y.val;
}

inline int get_gong(int x,int y) { //通过几行几列得到第几宫
    return (x-1)/3*3+(y-1)/3+1;
}

inline void change(int x,int y,int num,bool val) { //修改该数位置所在行列宫vis
    int th=get_gong(x,y);
    ha[x][num]=li[y][num]=go[th][num]=val;
}

inline int add_sum(int i,int j) {
    int sum=0;
    if(i==9||i==1||j==9||j==1) sum=a[i][j]*6;
    else if((i==2&&2<=j&&j<=8)||(i==8&&2<=j&&j<=8)||(j==8&&2<=i&&i<=8)||(j==2&&2<=i&&i<=8)) sum=a[i][j]*7;
    else if((i==3&&3<=j&&j<=7)||(i==7&&3<=j&&j<=7)||(j==7&&3<=i&&i<=7)||(j==3&&3<=i&&i<=7)) sum=a[i][j]*8;
    else if((i==4&&4<=j&&j<=6)||(i==6&&4<=j&&j<=6)||(j==6&&4<=i&&i<=6)||(j==4&&4<=i&&i<=6)) sum=a[i][j]*9;
    else if((i==5&&5<=j&&j<=5)||(i==5&&5<=j&&j<=5)||(j==5&&5<=i&&i<=5)||(j==5&&5<=i&&i<=5)) sum=a[i][j]*10;
    return sum;
}

inline int get_sum() {
    int sum=0;
    for(int i=1;i<=9;i++) {
        for(int j=1;j<=9;j++) {
            sum+=add_sum(i,j);
        }
    }
    return sum;
}
int lowbit(int x,int y,int th) {
    int sum=0;
    for(int i=1;i<=9;i++) {
        sum+=ha[x][i]&li[y][i]&go[th][i];
    }
    return sum;
}
bool fail=0;
int cont=0,maxans=0;
inline void dfs(int x,int y,int cnt) {
    if(cnt==cont+1) {
        maxans=max(maxans,int(get_sum()));
        fail=true;
        return ;
    }
    for(int i=1;i<=9;i++) {
        if(ha[x][i]&&li[y][i]&&go[get_gong(x,y)][i]) {
            a[x][y]=i;
            change(x,y,i,false);
            dfs(srt[cnt+1].id.first,srt[cnt+1].id.second,cnt+1);
            a[x][y]=0;
            change(x,y,i,true);
        }
    }
    return ;
}

void solve() {
    fail=0;
    for(int i=1;i<=9;i++) {
        for(int j=1;j<=9;j++) {
            ha[i][j]=li[i][j]=go[i][j]=true;
        }
    }
    for(int i=1;i<=9;i++) {
        for(int j=1;j<=9;j++) {
            cin>>a[i][j];
            if(a[i][j]) change(i,j,a[i][j],0);
        }
    }
    for(int i=1;i<=9;i++) {
        for(int j=1;j<=9;j++) {
            if(a[i][j]) continue;
            ++cont;
            srt[cont].val=lowbit(i,j,get_gong(i,j));
            srt[cont].id={i,j};
        }
    }
    sort(srt+1,srt+cont+1,cmp);
    srt[cont+1].id.first=srt[cont+1].id.second=78;
    dfs(srt[1].id.first,srt[1].id.second,1);
    if(!fail) {cout<<"-1\n";return ;}
    cout<<maxans<<"\n";
    return ;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    T=1;
    while(T--)solve();
    return 0;
}
2025/7/1 20:56
加载中...