题解 | #[NOIP2009]靶形数独#

题目描述

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

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

 

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

 

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

输入描述:

一共9行，每行9个整数（每个数都在0—9的范围内），表示一个尚未填满的数独方格，未填满的空格用“0”表示。每两个数字之间用一个空格隔开。

输出描述:

输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-1。

思路

#include<bits/stdc++.h>
using namespace std;
int mp[10][10]; //存储数独的图
int tabl[10][10]= {{0,0,0,0,0,0,0,0,0,0},
	{0,1,1,1,2,2,2,3,3,3},
	{0,1,1,1,2,2,2,3,3,3},
	{0,1,1,1,2,2,2,3,3,3},
	{0,4,4,4,5,5,5,6,6,6},
	{0,4,4,4,5,5,5,6,6,6},
	{0,4,4,4,5,5,5,6,6,6},
	{0,7,7,7,8,8,8,9,9,9},
	{0,7,7,7,8,8,8,9,9,9},
	{0,7,7,7,8,8,8,9,9,9},
}; //打表，方便判断小格
int tab2[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 hang[10][10],lie[10][10],xiaoge[10][10]; //行，列，小格的判断数组（0为未填，1为已填）
struct node {
	int num,x,y;
};
int maxn=-1;
vector<node>d,dt;
struct nnode{
	int id,num;
}hangjudge[10];
int cmp(struct nnode a,struct nnode b){
	return a.num<b.num;
}
int calc() {
	int ans=0;
	for(int i=1; i<=9; i++) {
		for(int j=1; j<=9; j++) {
			ans+=(tab2[i][j]*mp[i][j]);
		}
	}
	return ans;
}
void DFS(int n) { //n表示已经遍历完的格子，即遍历到第n+1个格子
	if(n==d.size()) {
		maxn=max(maxn,calc());
		return;
	}
	node tmp=d[n];
	int xx=tmp.x;
	int yy=tmp.y;
	for(int i=1; i<=9; i++) {
		if(!hang[xx][i] && !lie[yy][i] && !xiaoge[tabl[xx][yy]][i]) { //如果数字i同一行，同一列，同一小格都未出现，那么可以填入
			hang[xx][i]=1;
			lie[yy][i]=1;
			xiaoge[tabl[xx][yy]][i]=1;
			mp[xx][yy]=i;
			DFS(n+1); //第n+1个格子好了，遍历第n+2个格子
			hang[xx][i]=0; //回溯
			lie[yy][i]=0;
			xiaoge[tabl[xx][yy]][i]=0;
		}
	}
}
int main() {
	for(int i=1; i<=9; i++) {
		hangjudge[i].id=i;
		for(int j=1; j<=9; j++) {
			scanf("%d",&mp[i][j]);
			if(!mp[i][j]) {
				dt.push_back(node {i,i,j}); //将值为0的格子存入d中
				hangjudge[i].num++;
			} else {
				hang[i][mp[i][j]]=1; //第i行的mp[i][j]的值已被填过
				lie[j][mp[i][j]]=1; //第j列的mp[i][j]的值已被填过
				xiaoge[tabl[i][j]][mp[i][j]]=1; //第i个小方格中mp[i][j]已被填过
			}
		}
	}
	sort(hangjudge+1,hangjudge+10,cmp);
	for(int i=1; i<=9; i++) {
		for(auto j:dt) {
			if(j.num==hangjudge[i].id) d.push_back(j);
		}
	}
	DFS(0); //已经遍历完0个格子，即遍历到第一个格子
	printf("%d\n",maxn);
	return 0;
}