博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【NOIP2009】靶形数独
阅读量:5880 次
发布时间:2019-06-19

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

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

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

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

题解:

这个题目主要是要考虑枚举顺序,要从限制最多的地方开始枚举,这样才可能尽量少的拓展出状态;

所有我们对每个空格枚举每个数字看是否可行,找到可行数字最少的空格,从那里开始搜索。最后

打表统计一下答案就可以了。

#include
#include
#include
#include
#include
using namespace std;bool hen[10][10],zong[10][10],kuai[10][10][10];int map[10][10];int nowi,nowj,num=0;void getmin(){ int minn=10; for(int i=0;i<=8;i++){ for(int j=0;j<=8;j++){ if(map[i][j]) continue; int chance=9; for(int x=1;x<=9;x++){ if(hen[i][x]||zong[j][x]||kuai[i/3][j/3][x]) chance--; } if(minn>chance) minn=chance,nowi=i,nowj=j; } }}long long ans=0;void getans(){ long long anss=0; for(int i=0;i<=8;i++){ for(int j=0;j<=8;j++){ if(i==0||i==8||j==0||j==8) anss+=map[i][j]*6; else if (i==1||i==7||j==1||j==7) anss+=map[i][j]*7; else if (i==2||i==6||j==2||j==6) anss+=map[i][j]*8; else if (i==3||i==5||j==3||j==5) anss+=map[i][j]*9; else anss+=map[i][j]*10; } } ans=max(ans,anss);}void dfs(int i,int j,int numm){ //printf("%d %d %d\n",i,j,numm+num); if(numm+num==81) {getans();return;} for(int x=1;x<=9;x++){ if(hen[i][x]||zong[j][x]||kuai[i/3][j/3][x]) continue; hen[i][x]=1; zong[j][x]=1; kuai[i/3][j/3][x]=1; map[i][j]=x; getmin(); dfs(nowi,nowj,numm+1); hen[i][x]=0; zong[j][x]=0; kuai[i/3][j/3][x]=0; map[i][j]=0; }}int main(){ memset(hen,0,sizeof(hen)); memset(zong,0,sizeof(zong)); memset(kuai,0,sizeof(kuai)); for(int i=0;i<=8;i++){ for(int j=0;j<=8;j++){ int x; cin>>x; if(x==0) continue; map[i][j]=x; hen[i][x]=1; zong[j][x]=1; kuai[i/3][j/3][x]=1; num++; } } getmin(); dfs(nowi,nowj,0); if(ans!=0) printf("%d",ans); else printf("-1");}

 

转载于:https://www.cnblogs.com/renjianshige/p/7120866.html

你可能感兴趣的文章
如何使用网络视频服务器的权限管理
查看>>
WannaCry警示:学会检测和减轻云端恶意内容
查看>>
光纤将在5G发展中发挥关键作用
查看>>
思博伦推出Temeva平台:“云中测试”成为可能
查看>>
移动CRM风起云涌 千亿级市场显现
查看>>
韩国SK电讯宣布成功研发量子中继器
查看>>
TCP - WAIT状态及其对繁忙的服务器的影响
查看>>
安全预警:全球13.5亿的ARRIS有线调制解调器可被远程攻击
查看>>
麦子学院与阿里云战略合作 在线教育领军者技术实力被认可
查看>>
正确看待大数据
查看>>
Facebook通过10亿单词构建有效的神经网络语言模型
查看>>
2016股市投资风向标 大数据说了算
查看>>
发展大数据不能抛弃“小数据”
查看>>
25000个布满恶意软件的摄像头组成的僵尸网络
查看>>
FB全球开放360度直播功能 首先需要一个FB账号
查看>>
量子通信成信息安全领域发展重点 潜在市场望达1000亿元
查看>>
数据中心新的自动化运维技术
查看>>
OpenFlow下一步该怎么走?
查看>>
CoreOS为容器安全带来不同方法
查看>>
关于智慧城市建设要点问题的思考
查看>>