题目叫靶型数独，洛谷题号1074；
题目描述：要求在9*9宫格内填满数，分好的每个3*3宫格1到9数字不能重复，每行每列数字不能重复。
思想：dfs搜索。
我一开始想的是从头开始搜，每到一个格子，搜当前行当前列当前块块，把不能用的数标记。可是我没想到怎么同时维护当前行列坐标信息和选了哪一个（当然现在想到了），到最后到最后一个0时计算所有数值答案。反正思路极其混乱，然后看了有位叫做别人的大佬的代码深深折服，很清晰简略。当然这都是后话。
还是讲讲思路吧。
规定每个块，每行每列的编号，hang[i][j],lie[i][j],gong[i][j]==1表示i这个行/列/块的j数值已经有数存在了。
cnt表示0的标号，s数组记录每个0的行、列、块、价值信息方便用。
dfs函数写的非常简单。have提前计算已有价值。
其中算得上剪枝的是把每行0从小到大搜索，因为dfs是树形结构，深度小的越少搜索的数量越少。
找每个点的权值时利用了如果是第一层就会在第二层之前return，因此不用因为形如（2,1）这类点写一堆特判。
值得一提的是我最后忘了特判-1了，一直95分，非常的智障。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; long long maxn; int a[12][12],hang[12][12],lie[12][12],gong[12][12],s[90][8]; int have,cnt; struct llo{ int xx,ling; } e[12]; int kuai(int nx,int ny){ if(nx<=3){ if(ny<=3) return 1; if(ny<=6) return 2; if(ny<=9) return 3; } if(nx<=6){ if(ny<=3) return 4; if(ny<=6) return 5; if(ny<=9) return 6; } if(nx<=9){ if(ny<=3) return 7; if(ny<=6) return 8; if(ny<=9) return 9; } } bool cmp(llo x,llo y){ return x.ling<y.ling; } int val(int nx,int ny){ if(nx==1||ny==1||nx==9||ny==9) return 6; if(nx==2||ny==2||nx==8||ny==8) return 7; if(nx==3||ny==3||nx==7||ny==7) return 8; if(nx==4||ny==4||nx==6||ny==6) return 9; return 10; } void dfs(int num,long long v){ if(num==cnt+1){ maxn=max(maxn,v); return; } for(int i=1;i<=9;i++){ if(!hang[s[num][0]][i]&&!lie[s[num][1]][i]&&!gong[s[num][2]][i]){ hang[s[num][0]][i]=1; lie[s[num][1]][i]=1; gong[s[num][2]][i]=1; dfs(num+1,v+i*s[num][3]); hang[s[num][0]][i]=0; lie[s[num][1]][i]=0; gong[s[num][2]][i]=0; } } } int main(){ for(int i=1;i<=9;i++){ for(int j=1;j<=9;j++){ scanf("%d",&a[i][j]); if(a[i][j]){ hang[i][a[i][j]]=lie[j][a[i][j]]=gong[kuai(i,j)][a[i][j]]=1; have+=(a[i][j]*val(i,j)); } if(a[i][j]==0) e[i].ling++; e[i].xx=i; } } sort(e+1,e+10,cmp); for(int i=1;i<=9;i++){ for(int j=1;j<=9;j++){ if(a[e[i].xx][j]==0){ cnt++; s[cnt][0]=e[i].xx,s[cnt][1]=j,s[cnt][2]=kuai(e[i].xx,j),s[cnt][3]=val(e[i].xx,j); } } } dfs(1,have); if(maxn==0) printf("-1"); else printf("%lld",maxn); return 0; }