题目描述
小城和小华都是热爱数学的好学生,最近,他们不约而同地迷上了数独游戏,好胜的他们想用数独来一比高低。
但普通的数独对他们来说都过于简单了,于是他们向Z博士请教,Z博士拿出了他最近发明的“靶形数独”,作为这两个孩子比试的题目。
靶形数独的方格同普通数独一样,在9×9的大九宫格中有9个3×3的小九宫格(用粗黑色线隔开的)。
在这个大九宫格中,有一些数字是已知的,根据这些数字,利用逻辑推理,在其他的空格上填入1到9的数字。
每个数字在每个小九宫格内不能重复出现,每个数字在每行、每列也不能重复出现。
但靶形数独有一点和普通数独不同,即每一个方格都有一个分值,而且如同一个靶子一样,离中心越近则分值越高(如下图所示)。
上图具体的分值分布是:最里面一格(黄色区域)为10分,黄色区域外面的一圈(红色区域)每个格子为9分,再外面一圈(蓝色区域)每个格子为8分,蓝色区域外面一圈(棕色区域)每个格子为7分,最外面一圈(白色区域)每个格子为6 分,如上图所示。
比赛的要求是:每个人必须完成一个给定的数独(每个给定数独可能有不同的填法),而且要争取更高的总分数。
而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。
如图,在以下的这个已经填完数字的靶形数独游戏中,总分数为2829。
游戏规定,将以总分数的高低决出胜负。
由于求胜心切,小城找到了善于编程的你,让你帮他求出,对于给定的靶形数独,能够得到的最高分数。
样例
输入样例:
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
算法1
(搜索 + 剪枝)
与数独类似。需要注意搜索顺序。每次从9 x 9的方格中挑选出来,这个格子可以选择的次数最少的格子来搜索。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 9, M = 1 << N;
int ones[M], map[M];
int row[N], col[N], cell[3][3];
int g[N][N];
int ans = -1;
inline int lowbit(int x){
return x & -x;
}
void init(){
for (int i = 0; i < N; i ++ ) map[1 << i] = i; //lowbit只返回最低的1所在的位置构成的2进制数,需要打表转化成10进制
for (int i = 0; i < M; i ++ )
for (int j = i; j; j -= lowbit(j))
ones[i] ++;//打表计算所有的int范围内二进制数有多少个1
for (int i = 0; i < 9; i ++ ) row[i] = col[i] = cell[i / 3][i % 3] = M - 1; //全部初始化为1
}
inline int get_score(int x, int y, int t){//计算得分
return (min(min(x, 8 - x), min(y, 8 - y)) + 6) * t;
}
inline void draw(int x, int y, int t){
int s = 1;
if (t > 0) g[x][y] = t;
else {//当t小于0说明当前方格需要恢复现场
s = -1;
t = -t;
g[x][y] = 0;
}
t --;//需要将1~9 映射回到数组中的0 ~ 8方便操作。
row[x] -= (1 << t) * s;//这里就是s变量精髓的地方,如果填了数那么就减掉,如果恢复现场,那么就加上。
col[y] -= (1 << t) * s;
cell[x / 3][y / 3] -= (1 << t) * s;
}
inline int get(int x, int y){//计算坐标为x, y的方格可以填哪些数
return row[x] & col[y] & cell[x / 3][y / 3];
}
void dfs(int cnt, int score){
if (!cnt) {
ans = max(ans, score);
return ;
}
int minv = 10;
int x, y;
for (int i = 0; i < N; i ++ )//遍历整个9x9方格,首先寻找当前方格可以填的数最少的方格
for (int j = 0; j < N; j ++ )
if (!g[i][j]){//如果没填过数
int t = ones[get(i, j)];
if (t < minv){
minv = ones[get(i, j)];
x = i, y = j;
}
}
for (int i = get(x, y); i; i -= lowbit(i)){//开始填数
int t = map[lowbit(i)] + 1;
draw(x, y, t);
dfs(cnt - 1, score + get_score(x, y, t));
draw(x, y, -t);
}
}
int main(){
init();
int cnt = 0, score = 0;
for (int i = 0; i < N; i ++)
for (int j = 0; j < N; j ++ ){
int x;
cin >> x;
if (x){//如果当前位置有数字,先将这些数字的和累加
draw(i, j, x);
score += get_score(i, j, x);
}
else cnt ++;
}
dfs(cnt, score);
cout << ans << endl;
return 0;
}