这两天OD留的题是搜索，这个东西，就是历年的NOIP压轴题嘛。做了几道什么斗地主啊啥的，感觉还是这题我还懂点。
这道题的搜（xia）索（da）思路是这样的：预处理出一切能处理的东西。
数独大家都了解吧：每一行，每一列，每一个九宫格都要求不一样。
我们需要预处理出：
每个点的分数（废话）。每一行中确定的数。每一列中确定的数。每一个九宫格中确定的数。以及最开始确定部分的答案。
记录每个未确定点的坐标。搜他们就好啦（倒着搜一定要。我哪知道为啥）
对于每个点，就纯循环枚举1~9就好了。当然我们要判断剪枝。
当这行有这个数的时候，return
……
以此类推。
这样就算搜到重的也一下就退回来了。
还有，记得要回溯。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define pos2(i,a,b) for(int i=(a);i>=(b);i--)
#define N 200
#define inf 0x7fffffff
#define LL long long
int a[N][N],point[N][N];
int hang[N][N],lie[N][N],ge[N][N],cnt[N][N];
int ans,basic,ji=0;
struct haha{
int x,y;
}fei[100];
void init(){
point[5][5]=10;
pos(i,1,9) point[1][i]=point[9][i]=point[i][1]=point[i][9]=6;
pos(i,2,8) point[2][i]=point[8][i]=point[i][2]=point[i][8]=7;
pos(i,3,7) point[3][i]=point[7][i]=point[i][3]=point[i][7]=8;
pos(i,4,6) point[4][i]=point[6][i]=point[i][4]=point[i][6]=9;
ji=0;
pos(i,1,3){
pos(j,1,3){
cnt[i][j]=++ji;
}
}
ji=0;
pos(i,1,9){
pos(j,1,9){
scanf("%d",&a[i][j]);
if(a[i][j]!=0){
basic+=a[i][j]*point[i][j];//cout<<basic<<endl;
hang[i][a[i][j]]=1;lie[j][a[i][j]]=1;
int temp=i/3;temp+=i%3==0?0:1;int temp2=j/3;temp2+=j%3==0?0:1;
ge[cnt[temp][temp2]][a[i][j]]=1;
}
else{fei[++ji].x=i;fei[ji].y=j;}
}
}
}
void dfs(int last,int sum,int num){
if(hang[fei[last].x][num]==1) return;
if(lie[fei[last].y][num]==1) return;
int temp=fei[last].x/3;temp+=fei[last].x%3==0?0:1;int temp2=fei[last].y/3;temp2+=fei[last].y%3==0?0:1;
if(ge[cnt[temp][temp2]][num]==1) return;
if(last==1){ans=max(ans,sum);return;}
//cout<<last<<" sum="<<sum<<" num="<<num<<endl;
pos(i,1,9){
hang[fei[last].x][num]=1;lie[fei[last].y][num]=1;ge[cnt[temp][temp2]][num]=1;
dfs(last-1,sum+(i*point[fei[last-1].x][fei[last-1].y]),i);
hang[fei[last].x][num]=0;lie[fei[last].y][num]=0;ge[cnt[temp][temp2]][num]=0;
}
}
int main(){
//freopen("sudoku.in","r",stdin);
//freopen("sudoku.out","w",stdout);
init();
//cout<<"ji="<<ji<<endl;
pos(i,1,9)
dfs(ji,i*point[fei[ji].x][fei[ji].y],i);
if(ans==0) cout<<"-1";
else cout<<basic+ans;
return 0;
}