方法一：

TLE2个点

思路：找下一个可能的点dfs方法

std:

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
int getint(){
    int x=0,f=1; char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-f; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return f*x;
}
const int MAXN=12;
const int score[10][10]=
{{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6}};
int row[MAXN][MAXN],col[MAXN][MAXN],area[MAXN][MAXN],sdk[MAXN][MAXN];
int row_cnt[MAXN],col_cnt[MAXN],cnt,ans=-1;
inline int id(int i,int j){return (i-1)/3*3+1+(j-1)/3;}
inline int calc(){
    int tmp=0;
    for(int i=1;i<=9;++i)
        for(int j=1;j<=9;++j)
            tmp+=score[i][j]*sdk[i][j];
    return tmp;
}
void dfs(int r,int c,int cpl){    
    if(cpl==81){
        ans=max(ans,calc());
        return ;
    }
    for(int k=1;k<=9;++k){
        if(row[r][k]||col[c][k]||area[id(r,c)][k]) continue;
        row[r][k]=true;
        col[c][k]=true;
        area[id(r,c)][k]=true;
        row_cnt[r]++,col_cnt[c]++;
        sdk[r][c]=k;
        int tmpr=-1,nxt_r=0,tmpc=-1,nxt_c=0;
        for(int i=1;i<=9;++i)
            if(row_cnt[i]>tmpr&&row_cnt[i]<9)
                tmpr=row_cnt[i],nxt_r=i;
        for(int j=1;j<=9;++j)
            if(col_cnt[j]>tmpc&&(!sdk[nxt_r][j]))
                tmpc=col_cnt[j],nxt_c=j;
        dfs(nxt_r,nxt_c,cpl+1);
        row[r][k]=false;
        col[c][k]=false;
        area[id(r,c)][k]=false;
        row_cnt[r]--,col_cnt[c]--;
        sdk[r][c]=0;
    }
}
int main(){    
    for(int i=1;i<=9;++i){
        for(int j=1;j<=9;++j){
            sdk[i][j]=getint();
            if(sdk[i][j]!=0){
                row[i][sdk[i][j]]=true;
                col[j][sdk[i][j]]=true;
                area[id(i,j)][sdk[i][j]]=true;
                row_cnt[i]++,col_cnt[j]++;
                cnt++;
            }
        }
    }
    int tmpr=-1,r,tmpc=-1,c;
    for(int i=1;i<=9;++i)
        if(row_cnt[i]>tmpr&&row_cnt[i]<9)
            tmpr=row_cnt[i],r=i;
    for(int j=1;j<=9;++j)
        if(col_cnt[j]>tmpc&&(!sdk[r][j]))
            tmpc=col_cnt[j],c=j;
    dfs(r,c,cnt);
    cout<<ans<<endl;
}

方法二（正解）：

思路：还是用dfs，但加了剪枝，我们先预处理格子的顺序

特别长的代码111行

std:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int ans[15][15],sec[15][15],yuan[15][15],xy[90],res=-1;

bool hc[15][15],lc[15][15],jc[15][15];
void init()
{
	memset(sec,-1,sizeof(sec));
	for(int i=1;i<=9;i++)
		for(int j=1;j<=9;j++)
			sec[i][j]=0;
	int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},tot=0,t=0,po=6;
	int x=1,y=1;
	while(tot!=81)
	{
		tot++,sec[x][y]=po;
		if(sec[x+dx[t]][y+dy[t]]!=0)
		{
			t++;
			if(t==4)t=0,po++;
		}
		x+=dx[t],y+=dy[t];
	}
}

struct node{
	int sum,h;
}zero[10];

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

int getsum()
{
	int sum=0;
	for(int i=1;i<=9;i++)
		for(int j=1;j<=9;j++)
			sum+=sec[i][j]*ans[i][j];
	return sum;
}

void dfs(int tot)
{
	if(tot==82)
	{
		res=max(res,getsum());
		return ;
	}
	int x,y;
	if(xy[tot]%9==0)x=xy[tot]/9,y=9;
	else x=xy[tot]/9+1,y=xy[tot]%9;
	if(yuan[x][y]!=0)dfs(tot+1);
	else
	{
		int k=(x-1)/3,l=(y-1)/3+1;
		for(int i=1;i<=9;i++)
		{
			if(hc[x][i]||lc[y][i]||jc[k*3+l][i])continue;
			hc[x][i]=true;
			lc[y][i]=true;
			jc[k*3+l][i]=true;
			ans[x][y]=i;
			dfs(tot+1);
			hc[x][i]=false;
			lc[y][i]=false;
			jc[k*3+l][i]=false;
			ans[x][y]=0;
		}
	}
}

int main()
{
	init();
	for(int i=1;i<=9;i++)
	{
		int tot=0;
		for(int j=1;j<=9;j++)
		{
			scanf("%d",&yuan[i][j]);
			if(yuan[i][j]==0)
				tot++;
			else
			{
				ans[i][j]=yuan[i][j];
				hc[i][yuan[i][j]]=true;
				lc[j][yuan[i][j]]=true;
				int x=(i-1)/3,y=(j-1)/3+1;
				jc[x*3+y][yuan[i][j]]=true;
			}
		}
		zero[i].sum=tot,zero[i].h=i;
	}
	sort(zero+1,zero+10,cmp);
	int tot=0;
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			int h=zero[i].h;
			xy[++tot]=(h-1)*9+j;
		}
	}
	dfs(1);
	printf("%d\n",res);
    return 0;
}

知识点总结：

https://oi-wiki.org/search/dfs/

https://oi-wiki.org/search/alpha-beta/