85分,TLE 3个点,还能怎么优化
查看原帖
85分,TLE 3个点,还能怎么优化
547908
NightTide楼主2021/7/30 20:03
#include<bits/stdc++.h>
using namespace std;
const int score[9][9]={
                    6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 ,
                    6 ,7 ,7 ,7 ,7 ,7 ,7 ,7 ,6 ,
                    6 ,7 ,8 ,8 ,8 ,8 ,8 ,7 ,6 ,
                    6 ,7 ,8 ,9 ,9 ,9 ,8 ,7 ,6 ,
                    6 ,7 ,8 ,9 ,10,9 ,8 ,7 ,6 ,
                    6 ,7 ,8 ,9 ,9 ,9 ,8 ,7 ,6 ,
                    6 ,7 ,8 ,8 ,8 ,8 ,8 ,7 ,6 ,
                    6 ,7 ,7 ,7 ,7 ,7 ,7 ,7 ,6 ,
                    6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 ,
                };
struct coor{
    int x,y;
    int vis;
};
coor empty[100];
int cnt,ans=-1;
int broad[20][20];
bool f=true;
inline int cal(){
    int sum=0;
    for(register int i=0;i<9;i++){
        for(register int j=0;j<9;j++){
            sum+=broad[i][j]*score[i][j];
        }
    }
    return sum;
}
inline bool search(int n,int x,int y){
    for(register int i=0;i<9;i++){
        if(broad[x][i]==n){
            return true;
        }
    }
    for(register int i=0;i<9;i++){
        if(broad[i][y]==n){
            return true;
        }
    }
    int l=y/3*3,r=l+3;
    int t=x/3*3,b=t+3;
    for(register int i=l;i<r;i++){
        for(register int j=t;j<b;j++){
            if(broad[j][i]==n){
                return true;
            }
        }
    }
    return false;
}
inline void dfs(int step){
    if(step==cnt){
        ans=max(ans,cal());
        return ;
    }
    int mn=9, x=0, y=0;
    for(register int i=0;i<9;++i){
        for(register int j=0;j<9;++j){
            if(broad[i][j]==0){
                int scal=0;
                for(register int k=1;k<=9;++k){
                    if(!search(k,i,j)){
                        scal++;
                        if(scal>=mn) break;
                    }
                }
                if(scal<mn){
                    mn=scal;
                    x=i;
                    y=j;
                }
            }
        }
    }
    for(register int i=1;i<=9;i++){
        if(!search(i,x,y)){
            broad[x][y]=i;
            dfs(step+1);
            broad[x][y]=0;
        }
    }
}
int main(){
    // freopen("sudoku.in","r",stdin);
    // freopen("sudoku.out","w",stdout);
    for(register int i=0;i<9;i++){
        for(register int j=0;j<9;j++){
            scanf("%d",&broad[i][j]);
            if(broad[i][j]==0){
                empty[cnt].x=i;
                empty[cnt].vis=0;
                empty[cnt++].y=j;
            }
        }
    }
    dfs(0);
    cout<<ans<<endl;
    return 0;
}
/*
test1:
    7 0 0 9 0 0 0 0 1
    1 0 0 0 0 5 9 0 0
    0 0 0 2 0 0 0 8 0
    0 0 5 0 2 0 0 0 3
    0 0 0 0 0 0 6 4 8
    4 1 3 0 0 0 0 0 0
    0 0 7 0 0 2 0 9 0
    2 0 1 0 6 0 8 0 4
    0 8 0 5 0 4 0 1 2
*/
/*
test2:
    0 0 0 7 0 2 4 5 3
    9 0 0 0 0 8 0 0 0
    7 4 0 0 0 5 0 1 0
    1 9 5 0 8 0 0 0 0
    0 7 0 0 0 0 0 2 5
    0 3 0 5 7 9 1 0 8
    0 0 0 6 0 1 0 0 0
    0 6 0 9 0 0 0 0 1
    0 0 0 0 0 0 0 0 6
*/
2021/7/30 20:03
加载中...