#2 #4 #7 #8 #20TLE,75分,开了O2也是80分(最后一个过了)
查看原帖
#2 #4 #7 #8 #20TLE,75分,开了O2也是80分(最后一个过了)
373226
justinjia楼主2021/4/17 12:40

求助!!!

献上本蒟蒻的veryvery丑陋的代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char numbers[81];
const int pts[81]={
    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
};
bool row[9][10],column[9][10],block[9][10];
int ans=-1;
void dfs(int u){
    if(u==81){
        int sum=0;
        for(int i=0;i<81;i++)
            sum+=(numbers[i]-'0')*pts[i];
        ans=max(sum,ans);
    }
    if(numbers[u]!='0'){
        dfs(u+1);
        return;
    }
    for(int i=1;i<=9;i++){
        if(row[u/9][i]||column[u%9][i]||block[u/27*3+u%9/3][i])
            continue;
        row[u/9][i]=1;
        column[u%9][i]=1;
        block[u/27*3+u%9/3][i]=1;
        numbers[u]=i+'0';
        dfs(u+1);
        numbers[u]='0';
        row[u/9][i]=0;
        column[u%9][i]=0;
        block[u/27*3+u%9/3][i]=0;
    }
}
int main(void){
    memset(row,0,sizeof(row));
    memset(column,0,sizeof(column));
    memset(block,0,sizeof(block));
    for(int i=0;i<81;i++){
        char tmp[2];
        scanf("%s",tmp);
        numbers[i]=tmp[0];
        if(numbers[i]!='0'){
            row[i/9][numbers[i]-'0']=1;
            column[i%9][numbers[i]-'0']=1;
            block[i/27*3+i%9/3][numbers[i]-'0']=1;
        }
    }
    dfs(0);
    printf("%d",ans);
    return 0;
}
2021/4/17 12:40
加载中...