Aimee

思维难度没有

唯一的剪枝就是从0少的列开始搜索

记录下所有能放的点的坐标，按顺序搜索

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct ha{
    int id;
    int sum;
} num[10];
int ma[10][10],h[10][10];
int l[10][10];
int g[10][10];
int need[101][10];
int x,y,ans=-1;
int p;
int ready;
bool cmp(ha x,ha y){
    return x.sum<y.sum;
}
int which(int i,int j)
{
    if(i<=3){
        if(j<=3)        return 1;
        else if(j<=6)   return 2;
        else            return 3;
    }
    else if(i<=6){
        if(j<=3)        return 4;
        else if(j<=6)    return 5;
        else            return 6;
    }
    else{
        if(j<=3)        return 7;
        else if(j<=6)   return 8;
        else            return 9;
    }
}
int point(int i,int j)
{
    if(i==1||j==1||i==9||j==9)   return 6;
    if(i==2||j==2||i==8||j==8)     return 7;
    if(i==3||j==3||i==7||j==7)   return 8;
    if(i==4||j==4||i==6||j==6)   return 9;
    return 10;
}
void dfs(int now,int sum){
//  cout<<now<<endl;
    if(now==p){
    //  cout<<"SS";
        ans=max(ans,sum);
        return ;
    }
    for(int  i=1;i<=9;++i){
        if(!h[need[now][0]][i]&&!l[need[now][1]][i]){
            if(!g[need[now][3]][i]){
                h[need[now][0]][i]=l[need[now][1]][i]=g[need[now][3]][i]=1;
                dfs(now+1,sum+(need[now][2]*i));
                    h[need[now][0]][i]=l[need[now][1]][i]=g[need[now][3]][i]=0;
            }
        }
    }
}
int main(){
    for(int i=1;i<=9;++i){
        num[i].id=i;
    }
    for(int i=1;i<=9;++i){
        for(int j=1;j<=9;++j){
            scanf("%d",&ma[i][j]);
            if(ma[i][j]==0){
                num[i].sum++;
            }else{
                h[i][ma[i][j]]=1;
                l[j][ma[i][j]]=1;
                g[which(i,j)][ma[i][j]]=1;
                ready+=ma[i][j]*point(i,j);
            }
        }
    }
    sort(num+1,num+9+1,cmp);
    for(int i=1;i<=9;++i){
        for(int j=1;j<=9;++j){
            if(ma[num[i].id][j]==0){
                need[p][0]=num[i].id;
                need[p][1]=j;
                need[p][2]=point(num[i].id,j);
                need[p][3]=which(num[i].id,j);
                p++;
            }
        }
    }
    dfs(0,ready);
    printf("%d",ans);
    return 0;
}