一道挺水的DFS。

题目详情

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 ZZ 博士请教，ZZ 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。

靶形数独的方格同普通数独一样，在 9×99 \times 9 格高的大九宫格中有 99 个 3×33 \times 3 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 11 到 99 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）

image.png

上图具体的分值分布是：最里面一格（黄色区域）为 1010 分，黄色区域外面的一圈（红色区域）每个格子为 99 分，再外面一圈（蓝色区域）每个格子为 88 分，蓝色区域外面一圈（棕色区域）每个格子为 77 分，最外面一圈（白色区域）每个格子为 66 分，如上图所示。比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为 28292829 。游戏规定，将以总分数的高低决出胜负。

image.png

由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。

做法

这道题爆搜肯定不行，所以要像平时做数独时一样，从 00 少的地方开始搜索。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
using namespace std;
struct countxy{
	int rank,sum;
}data[10];
int x[10][10],y[10][10],all[10][10],a[10][10],s[100][4];
int u,maxans=-1,nowscore;
int getpoint_DJX(int i,int j){
	if(i==1 or j==1 or i==9 or j==9)return 6;
	else if(i==2 or j==2 or i==8 or j==8)return 7;
	else if(i==3 or j==3 or i==7 or j==7)return 8;
	else if(i==4 or j==4 or i==6 or j==6)return 9;
	else return 10;
}
bool cmp(countxy a,countxy b){
	return a.sum<b.sum; 
}
int getpoint_xy(int i,int j){
	if(i<=3){
		if(j<=3)return 1;
		else if(j<=6)return 2;
		else return 3;
	}
	else if(i<=6){
		if(j<=3)return 4;
		else if(j<=6)return 5;
		else return 6;
	}
	else{
		if(j<=3)return 7;
		else if(j<=6)return 8;
		else return 9;
	}
}
void dfs(int p,int score){
	if(p==u){
		if(score>maxans)maxans=score;
		return;
	}
	for(int i=1;i<=9;i++){
		if(!x[s[p][0]][i] and !y[s[p][1]][i] and !all[s[p][3]][i]){
			x[s[p][0]][i]=y[s[p][1]][i]=all[s[p][3]][i]=1;
			dfs(p+1,score+(s[p][2]*i));
			x[s[p][0]][i]=y[s[p][1]][i]=all[s[p][3]][i]=0;
		}
	}
}
void Init(){
	freopen("sudoku.in","r",stdin);
	freopen("sudoku.out","w",stdout);
	for(int i=1;i<=9;i++){
		data[i].rank=i;
	}
}
void ReadData(){
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			scanf("%d",&a[i][j]);
			if(a[i][j]>0){
				nowscore+=a[i][j]*getpoint_DJX(i,j);
				x[i][a[i][j]]=y[j][a[i][j]]=all[getpoint_xy(i,j)][a[i][j]]=1;
			}
			else data[i].sum++;
		}
	}
	sort(data+1,data+10,cmp);
}
void OutPutAns(){
	printf("%d",maxans);
}
void Work(){
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			if(a[data[i].rank][j]==0){
				s[u][0]=data[i].rank,s[u][1]=j;
				s[u][2]=getpoint_DJX(data[i].rank,j);
				s[u++][3]=getpoint_xy(data[i].rank,j);
			}
		}
	}
}
void Search(){
	dfs(0,nowscore);
}
int main(){
	Init();
	ReadData();
	Work();
	Search();
	OutPutAns();
	return 0;
}

视频版讲解