链接：https://ac.nowcoder.com/acm/contest/23156/1035
来源：牛客网
来源：牛客网
题目描述
小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向Z博士请教，Z博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。
靶形数独的方格同普通数独一样，在9格宽×9格高的大九宫格中有9个3格宽×3格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入1到9的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）
上图具体的分值分布是：最里面一格（黄***域）为10分，黄***域外面的一圈（红***域）每个格子为9分，再外面一圈（蓝***域）每个格子为8分，蓝***域外面一圈（棕***域）每个格子为7分，最外面一圈（白***域）每个格子为6分，如上图所示。比赛的要求是：每个人必须完成一个给定的数独（每个给定数独有可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下这个已经填完数字的靶形数独游戏中，总分为2829。游戏规定，将以总分数的高低决出胜负。
由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。
输入描述:
一共9行，每行9个整数（每个数都在0—9的范围内），表示一个尚未填满的数独方格，未填满的空格用“0”表示。每两个数字之间用一个空格隔开。
输出描述:
输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-1。
思路
这题是数独的进阶版（虽然并没有进阶多少，本质上还是算出所有可能的数独，分别对这些可能的数独求总分，取其中的最大值）
数独的基本版本题：1010-数独挑战_2021秋季算法入门班第六章习题：搜索与搜索剪枝
所以本质上还是DFS，并且DFS的方法可以和原本的数独一样。
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
这是本人对于原本的数独题的理解：题解 | #数独挑战#_牛客博客
因为求唯一解-->用DFS解决，使用回溯法
注意DFS递归到最大深度时就直接计算，不要递归完了再计算
DFS的一层递归判断条件为：这个数字在这一列，这一行，这一个小格内均未出现。
DFS的可以计算分数条件为：全部空缺的数字已填入
注：这里有一个小技巧，用于方便的判断某个数字属于哪一个小格内，就是打表（看tabl[10][10]数组，用于表示位置为mp[x][y]的数字属于哪一个小格）
虽然也可以用其他方法判断，但是这个更加方便直观一些
附上那一题最原始的数独的代码
#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 hang[10][10],lie[10][10],xiaoge[10][10]; //行，列，小格的判断数组（0为未填，1为已填）
struct node{
int x,y;
};
vector<node>d;
void print(){
for(int i=1; i<=9; i++) {
for(int j=1; j<=9; j++) {
if(j==1) printf("%d",mp[i][j]);
else printf(" %d",mp[i][j]);
}
printf("\n");
}
}
void DFS(int n) { //n表示已经遍历完的格子，即遍历到第n+1个格子
if(n==d.size()){
print(); //这里直接输出，不要递归完了再输出
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++) {
for(int j=1; j<=9; j++) {
scanf("%d",&mp[i][j]);
if(!mp[i][j]){
d.push_back(node{i,j}); //将值为0的格子存入d中
}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]已被填过
}
}
}
DFS(0); //已经遍历完0个格子，即遍历到第一个格子
return 0;
}
这一题计算分数时也可以使用打表的方法
但是如果直接这样求解的话，理论上答案是全部正确的，但是会TLE（由于递归判断的点数过多的问题）
所以需要转换一下思维：即计算每一行空缺数字的个数，然后优先对空缺数字少的行数进行遍历，这样可以一定程度上减少运行时间（事实上也正是如此，最后AC了）
所以代码中新增了一个统计每行空缺数字个数的hangjudge数组，统计完成后sort升序排序一下，再把存储点的位置坐标的数组根据hangjudge数组的排序方式来排序，从而使得DFS中的点按行中空缺数字个数少的来遍历
运行时间在300ms-400ms左右
本题难度一般：会用DFS求解普通数独的基本都不存在WA的问题，就是TLE的问题，改变一下顺序就行了
代码如下（本质不变，就是调整了一下点的排列顺序，以及输出的函数改成了计算分数取其最大值的函数）：
#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;
}
京公网安备 11010502036488号