题意没玩过数独的先看一下规则应该没人没玩过吧数独盘面是九个宫以粗实线划分每一宫又分为九个小格。在空格上填入1-9的数字使1-9每个数字在每一行、每一列和每一宫中都只出现一次。你需要填一个数独但有一点和普通的不一样你要使填好后数独的分数最高。每个格子获得的分数是 这个格子本身的分值×格子上填的数整个数独的分数是每个格子的分数之和。每个格子本身的分值如下图用颜色区分不同区域如图在以下的这个已经填完数字的靶形数独游戏中总分数为282928292829。下图也是样例的最优解样例输入7 0 0 9 0 0 0 0 1 1 0 0 0 0 5 9 0 0 0 0 0 2 0 0 0 8 0 0 0 5 0 2 0 0 0 3 0 0 0 0 0 0 6 4 8 4 1 3 0 0 0 0 0 0 0 0 7 0 0 2 0 9 0 2 0 1 0 6 0 8 0 4 0 8 0 5 0 4 0 1 2样例输出2829数据规模对于40%40\%40%的数据数独中非000数的个数不少于303030对于80%80\%80%的数据数独中非000数的个数不少于262626对于100%100\%100%的数据数独中非000数的个数不少于242424。思路分析阶段1可以想到一个较为简单的做法就是用dfs枚举每个空格填什么全部填完之后再判断每行、每列、每个宫格是否有重复的如果没有就算出分数计入答案。时间复杂度最多有575757个空格每个空格有9种填法也就是9^57实在是太恐怖了计算器都不给我一个确切的答案。阶段2要避免一些肯定不对的情况就要一边填一边判断当前这一行这一列这一宫格有没有出现重复的数字可以建立boolboolbool数组fr[i][j]fr[i][j]fr[i][j]fc[i][j]fc[i][j]fc[i][j]f[i][j]f[i][j]f[i][j]分别表示第iii行第iii列第iii个宫格是否已经有数字jjj了代码如下getid(x,y)getid(x,y)getid(x,y)是用来获取第xxx行第yyy列的格子是属于哪个宫格的for(inti1;i9;i)if(!fr[x][i]!fc[y][i]!f[getid(x,y)][i]){fr[x][i]1,fc[y][i]1,f[getid(x,y)][i]1;rec[x][y]i;if(y9)dfs(x1,1);elsedfs(x,y1);fr[x][i]0,fc[y][i]0,f[getid(x,y)][i]0;}阶段3然而上面的代码只有80分于是考虑用一些玄学卡常优化。我们统计出每一行有多少个000并将这些行按照000的个数从小到大排序先填000个数少的行dfsdfsdfs本来就是一行行填入的。这样做能使枚举的情况数量变少到后面有很多未知的行的时候已经填好了很多行可以剪掉很多情况。由于打乱原本的数组会导致所属的宫格无法判断所以我用一个structstructstruct存了每行的编号ididid和000的数量cntcntcnt单独排好序用headheadhead存储000最少的是第几行nex[i]nex[i]nex[i]记录按照000的数量排序后第iii行的下面一行是第几行形成一个记录顺序的链表。完整的代码奉上只要用nex[x]nex[x]nex[x]替换之前的x1x1x1即可#includebits/stdc.husingnamespacestd;inta[10][10],rec[10][10],ans,head,nex[10];boolfr[10][10],fc[10][10],f[10][10];intscore[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}};//每个格子的分值我采用了打表可能有更好的方法structnode{intid,cnt;}n[10];boolcmp(node x,node y){returnx.cnty.cnt;}intgetid(inti,intj){if(i3){if(j3)return1;elseif(j7)return3;elsereturn2;}elseif(i7){if(j3)return7;elseif(j7)return9;elsereturn8;}else{if(j3)return4;elseif(j7)return6;elsereturn5;}}voiddfs(intx,inty){if(x0){intres0;for(inti1;i9;i)for(intj1;j9;j)resrec[i][j]*score[i][j];ansmax(ans,res);return;}if(a[x][y]){rec[x][y]a[x][y];if(y9)dfs(nex[x],1);elsedfs(x,y1);}else{for(inti1;i9;i)if(!fr[x][i]!fc[y][i]!f[getid(x,y)][i]){fr[x][i]1,fc[y][i]1,f[getid(x,y)][i]1;rec[x][y]i;if(y9)dfs(nex[x],1);elsedfs(x,y1);fr[x][i]0,fc[y][i]0,f[getid(x,y)][i]0;}}}intmain(){for(inti1;i9;i)n[i].idi;for(inti1;i9;i)for(intj1;j9;j){scanf(%d,a[i][j]);n[i].cnt(a[i][j]0);fr[i][a[i][j]]1;fc[j][a[i][j]]1;f[getid(i,j)][a[i][j]]1;}sort(n1,n10,cmp);headn[1].id;for(inti1;i9;i)nex[n[i].id]n[i1].id;dfs(head,1);if(ans0)printf(-1\n);elseprintf(%d\n,ans);return0;}