搜索(靶形数独)
发布日期:2022-02-22 18:04:14 浏览次数:10 分类:技术文章

本文共 2608 字,大约阅读时间需要 8 分钟。

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

 

 

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

上图具体的分值分布是:最里面一格(黄色区域)为 1010 分,黄色区域外面的一圈(红色区域)每个格子为 99 分,再外面一圈(蓝色区域)每个格子为 88 分,蓝色区域外面一圈(棕色区域)每个格子为 77 分,最外面一圈(白色区域)每个格子为 66 分,如上图所示。比赛的要求是:每个人必须完成一个给定的数独(每个给定数独可能有不同的填法),而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和

总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图,在以下的这个已经填完数字的靶形数独游戏中,总分数为 2829。游戏规定,将以总分数的高低决出胜负。

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

输入输出格式

输入格式:

 

一共 99 行。每行 99 个整数(每个数都在 0-909 的范围内),表示一个尚未填满的数独方格,未填的空格用“ 00 ”表示。每两个数字之间用一个空格隔开。

 

输出格式:

 

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

 

输入输出样例

输入样例#1: 
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
输出样例#1: 
2829
输入样例#2: 
0 0 0 7 0 2 4 5 3 9 0 0 0 0 8 0 0 0 7 4 0 0 0 5 0 1 0 1 9 5 0 8 0 0 0 0 0 7 0 0 0 0 0 2 5 0 3 0 5 7 9 1 0 8 0 0 0 6 0 1 0 0 0 0 6 0 9 0 0 0 0 1 0 0 0 0 0 0 0 0 6
输出样例#2: 
2852 搜索 记录每一行每一列每一个块内数出现的次数 用一个队列(假)存储需要被填值的点可以精简代码 code:
#include
#include
#include
#include
using namespace std;int soc[10][10]={ {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 pos[10][10]={ {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];int lie[10][10];int block[10][10];int sp[1000][10];int mp[10][10];int preans;int snt;int ans=-1;struct zerocnt{ int cnt; int id; friend bool operator<(const zerocnt& a,const zerocnt & b){ return a.cnt
snt){ ans=max(ans,nowans); return ; } int x=sp[dep][1]; int y=sp[dep][2]; // cout<
<<' '<
<
>x; mp[i][j]=x; if(x){ hang[i][x]=1; lie[j][x]=1; block[pos[i][j]][x]=1; preans+=x*soc[i][j]; }else{ bian[i].cnt++; } } bian[i].id=i; } sort(bian+1,bian+10,less
()); for(int i=1;i<=9;++i){ int h=bian[i].id; for(int j=1;j<=9;++j){ if(!mp[h][j]){ sp[++snt][1]=h,sp[snt][2]=j; } } } dfs(1,preans); cout<
<

  

转载于:https://www.cnblogs.com/eric-walker/p/9427084.html

转载地址:https://blog.csdn.net/dengxingrao0615/article/details/102231346 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:旋转立方体实现
下一篇:bzoj2301 problem b

发表评论

最新留言

感谢大佬
[***.8.128.20]2024年03月11日 13时35分41秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php7.1解压包安装,【Swoole】php7.1安装swoole扩展 2019-04-21
linux centos删除安装的包,CentOS yum认为已删除的软件包仍在安装中 2019-04-21
酒店管理系统c语言带注释,酒店管理系统--C语言版.pdf 2019-04-21
c语言 实现sizeof功能,C语言简单实现sizeof功能代码 2019-04-21
c语言sin函数近似值,用泰勒公式求sin(x)的近似值 2019-04-21
c 语言登录系统源代码,c语言源代码---------------个人图书管理系统 2019-04-21
android线程通信方式,Android 主线程和子线程通信问题 2019-04-21
cps1 cps2 android,图文教程:CPS1和CPS2模拟器使用 2019-04-21
在线设计 html5 表单,html5注册表单制作-表单制作-小程序表单制作 2019-04-21
android小闹钟课程设计,《小闹钟》教学设计 2019-04-21
mysql文件系统_MySQL文件系统先睹为快(1) 2019-04-21
nums在python_程序找到一对(i,j),其中nums [i] + nums [j] +(i -j)在Python中最大化?... 2019-04-21
jquery后台内容管理_教育平台项目后台管理系统:课程内容模块 2019-04-21
grouping函数 mysql_sql聚合函数有哪些 2019-04-21
python os.walk如何不遍历隐藏文件_python 获取文件下所有文件或目录os.walk()的实例... 2019-04-21
python 股票估值_【中金固收·固收+】隐藏价值的角落:限售股AAP估值及Python实现方法(上)... 2019-04-21
java文档生成_Java文档自动生成 2019-04-21
java 共享目录_java 操作windows 共享目录方法介绍 2019-04-21
java 监控 宕机_JAVA监测tomcat是否宕机,控制重启 2019-04-21
catch that cow java_POJ3278——Catch That Cow 2019-04-21