列表

详情

NC50249. 靶形数独

描述

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向Z博士请教，Z博士拿出了他最近发明的「靶形数独」，作为这两个孩子比试的题目。
靶形数独的方格同普通数独一样，在9格宽9格高的大九宫格中有9个3格宽3格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入1到9的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）
28.png上图具体的分值分布是：里面一格（黄色区域）为10分，黄色区域外面的一圈（红色区域）每个格子为9分，再外面一圈（蓝色区域）每个格子为8分，蓝色区域外面一圈（棕色区域）每个格子为7分，外面一圈（白色区域）每个格子为6分，如上图所示。
比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。
如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为2829。游戏规定，将以总分数的高低决出胜负。
29.png由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的高分数。

输入描述

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

输出描述

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

示例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

输出: 

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

输出: 

2852

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 470ms, 内存消耗: 488K, 提交时间: 2020-02-26 13:05:05 

#include<cstdio>
#include<algorithm>
using namespace std;
 
int ans=-1,a[10][10],b[10][10],c[10][10];
bool f1[10][10],f2[10][10],f3[10][10];
 
void dfs(int step)
{
  int i,j,k,s,xx,yy,zz=10;
 
  for(i=1;i<=9;i++)
    for(j=1;j<=9;j++)if(a[i][j]==0)
      {
        for(s=0,k=1;k<=9;k++)
          if(!f1[c[i][j]][k] && !f2[i][k] && !f3[j][k])s++;
        if(s<zz)zz=s,xx=i,yy=j; 
      }
  
  if(zz==10)
    {
      for(k=0,i=1;i<=9;i++)
        for(j=1;j<=9;j++)
          k+=a[i][j]*b[i][j];
      ans=max(ans,k);
      return;
    }
    
  if(zz==0)return;
  
  for(k=1;k<=9;k++)
    if(!f1[c[xx][yy]][k] && !f2[xx][k] && !f3[yy][k])
      {
        a[xx][yy]=k;
        f1[c[xx][yy]][k]=f2[xx][k]=f3[yy][k]=1;
        
		dfs(step+1);
        
        a[xx][yy]=0;
		f1[c[xx][yy]][k]=f2[xx][k]=f3[yy][k]=0; 
      }
}
 
int main()
{
  int i,j,k;
  for(i=1;i<=9;i++)
    for(j=1;j<=9;j++)
      {
        scanf("%d",&a[i][j]);
        b[i][j]=10-max(abs(i-5),abs(j-5));
        c[i][j]=(i-1)/3*3+(j-1)/3+1;
        
        f1[c[i][j]][a[i][j]]=1;
	    f2[i][a[i][j]]=1;
	    f3[j][a[i][j]]=1;
	  }
  dfs(1);
  printf("%d\n",ans);
  return 0;
}

C++14(g++5.4) 解法, 执行用时: 577ms, 内存消耗: 488K, 提交时间: 2020-06-21 00:13:06 

#include<cstdio>
#include<algorithm>
using namespace std;
int ans=-1,a[10][10],b[10][10],c[10][10];
bool f1[10][10],f2[10][10],f3[10][10];
void dfs(int step) {
	int i,j,k,s,xx,yy,zz=10;

	for(i=1; i<=9; i++)
		for(j=1; j<=9; j++)
			if(a[i][j]==0) {
				for(s=0,k=1; k<=9; k++)
					if(!f1[c[i][j]][k] && !f2[i][k] && !f3[j][k])
						s++;
				if(s<zz){
					zz=s;
					xx=i;
					yy=j;
				} 
			}
	if(zz==10) {
		for(k=0,i=1; i<=9; i++)
			for(j=1; j<=9; j++)
				k+=a[i][j]*b[i][j];
		ans=max(ans,k);
		return;
	}

	if(zz==0)return;

	for(k=1; k<=9; k++)
		if(!f1[c[xx][yy]][k] && !f2[xx][k] && !f3[yy][k]) {
			a[xx][yy]=k;
			f1[c[xx][yy]][k]=f2[xx][k]=f3[yy][k]=1;

			dfs(step+1);

			a[xx][yy]=0;
			f1[c[xx][yy]][k]=f2[xx][k]=f3[yy][k]=0;
		}
}

int main() {
	int i,j,k;
	for(i=1; i<=9; i++)
		for(j=1; j<=9; j++) {
			scanf("%d",&a[i][j]);
			b[i][j]=10-max(abs(i-5),abs(j-5));  // 分值 
			c[i][j]=(i-1)/3*3+(j-1)/3+1;    // 方块 

			f1[c[i][j]][a[i][j]]=1;  //方块内只能有一个 
			f2[i][a[i][j]]=1;    // 同一行只能有一个 
			f3[j][a[i][j]]=1;    // 同一列只能有一个 
		}
	dfs(1);
	printf("%d\n",ans);
	return 0;
}

上一题

© 2025 nowcoder.com