【题解】洛谷P1074 [NOIP2009TG] 靶形数独（DFS+剪枝）
洛谷P1074：https://www.luogu.org/problemnew/show/P1074
思路
这道题一看就是DFS
打一个分数表方便后面算分
我用x y z数组分别表示行 列 宫 是否有放置数字
用cnt结构体中no和zero分别表示每行行号和每行的零的数量（下面会讲到为什么）
我们把每行按照零的数量从小到大排序 并保留行号来计算（因为搜索的层数与每行0的个数有关）
我们用一个队列q表示有几个点要枚举
然后我们从零最少的那行开始枚举就ok了
PS：ans一开始要赋值为-1 因为有无解的情况要输出-1（没有判无解的话95分 别问我咋知道的）
代码
#include<iostream> #include<algorithm> using namespace std; 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 ans=-1,k,maxn; int map[10][10],q[1010][4]; bool x[10][10],y[10][10],z[10][10]; struct date { int no; int zero; }cnt[10]; bool cmp(date a,date b) { return a.zero<b.zero; } int g(int ii,int jj)//判断宫 { if(ii<=3) { if(jj<=3) return 1; else if(jj<=6) return 2; else return 3; } else if(ii<=6) { if(jj<=3) return 4; else if(jj<=6) return 5; else return 6; } else { if(jj<=3) return 7; else if(jj<=6) return 8; else return 9; } } void cinn() { for(int i=1;i<=9;i++) { cnt[i].no=i;//记录行号 for(int j=1;j<=9;j++) { cin>>map[i][j]; if(map[i][j]!=0) { maxn+=map[i][j]*score[i][j];//预算本来就有的分数 x[i][map[i][j]]=1; y[j][map[i][j]]=1; z[g(i,j)][map[i][j]]=1;//把行列宫记录 } else cnt[i].zero++;//计算0的个数 } } } void dfs(int now,int sum)//now为队列中第几个点 sum为总分 { if(now>k)//如果队列中的每个点都被枚举过了 { ans=max(sum,ans);//找出最大值 return; } for(int i=1;i<=9;i++)//枚举数字 if(!x[q[now][1]][i]&&!y[q[now][2]][i]&&!z[q[now][3]][i])//如果行列宫均没有用过这个数字 { x[q[now][1]][i]=y[q[now][2]][i]=z[q[now][3]][i]=1;//行列宫记录 map[q[now][1]][q[now][2]]=i;//记录这个数字 dfs(now+1,sum+score[q[now][1]][q[now][2]]*map[q[now][1]][q[now][2]]); x[q[now][1]][i]=y[q[now][2]][i]=z[q[now][3]][i]=0;//还原操作 map[q[now][1]][q[now][2]]=0; } } int main() { cinn(); sort(1+cnt,1+9+cnt,cmp);//排序 for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) { if(!map[cnt[i].no][j]) { q[++k][1]=cnt[i].no; q[k][2]=j; q[k][3]=g(cnt[i].no,j); } } dfs(1,maxn); cout<<ans; }