问题描述
小城和小华都是热爱数学的好学生, 最近, 他们不约而同地迷上了数独游戏, 好胜的他 们想用数独来一比高低. 但普通的数独对他们来说都过于简单了, 于是他们向 Z 博士请教, Z 博士拿出了他最近发明的 “靶形数独”, 作为这两个孩子比试的题目.
靶形数独的方格同普通数独一样, 在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格高的小九宫格 (用粗黑色线隔开的). 在这个大九宫格中, 有一些数字是已知的, 根据这些 数字, 利用逻辑推理, 在其他的空格上填入 1 到 9 的数字. 每个数字在每个小九宫格内不能 重复出现, 每个数字在每行、每列也不能重复出现. 但靶形数独有一点和普通数独不同, 即每一个方格都有一个分值, 而且如同一个靶子一样, 离中心越近则分值越高. (如图)
上图具体的分值分布是: 最里面一格 (黄色区域) 为 10 分, 黄色区域外面的一圈 (红色区域) 每个格子为 9 分, 再外面一圈 (蓝色区域) 每个格子为 8 分, 蓝色区域外面一圈 (棕色区域) 每个格子为 7 分, 最外面一圈 (白色区域) 每个格子为 6 分, 如上图所示. 比赛的要求是: 每个人必须完成一个给定的数独 (每个给定数独可能有不同的填法), 而且要争取更高的总分数. 而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字 的乘积的总和. 如图, 在以下的这个已经填完数字的靶形数独游戏中, 总分数为 2829. 游戏规定, 将以总分数的高低决出胜负.
由于求胜心切, 小城找到了善于编程的你, 让你帮他求出, 对于给定的靶形数独, 能够得到的最高分数.
输入
输入文件名为 sudoku. in.
一共 9 行. 每行 9 个整数 (每个数都在 0--9 的范围内), 表示一个尚未填满的数独方 格, 未填的空格用 “0” 表示. 每两个数字之间用一个空格隔开.
输出
输出文件 sudoku. out 共 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输出样例 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数据范围
40% 的数据, 数独中非 0 数的个数不少于 30.
80% 的数据, 数独中非 0 数的个数不少于 26.
100% 的数据, 数独中非 0 数的个数不少于 24.
Explanation
这一道题看上去就是暴搜了对不对, 所以我们本来应该写的暴搜.
但是 JerrySkywalker 告诉我还有一个好东西叫 Dancing Links X, 毕竟是 Donald Knuth 发明的好东西 (但是速度似乎比爆搜还要慢上 60000 倍而且写了半天写不出来的说). 于是 就先写了一半的矩阵生成.
中间的也没有贴上, 因为反正也不想写了. 我觉得精确最小覆盖的问题我以后应该好好地 研究一下.
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef long long lli;
const int maxn = 400, maxm = 10;
int get_box(int x, int y) { return (y <= 3 ? 1 : (y <= 6 ? 2 : 3)) * 3 - 3 + (x <= 3 ? 1 : (x <= 6 ? 2 : 3)); }
int get_weight(int x, int y) { return 10 - min(abs(y - 5), abs(x - 5)); }
class Matrix
{
public:
int n, m; // Columns = 324, Rows (dynamic)
int arr[10 * maxn][maxn];
void new_row(void) { m++; }
void set_val_pos(int x, int y, int weight) {
arr[m][(y - 1) * 9 + x] = weight; }
void set_val_row(int y, int val, int weight) {
arr[m][81 + (y - 1) * 9 + val] = weight; }
void set_val_col(int x, int val, int weight) {
arr[m][81 * 2 + (x - 1) * 9 + val] = weight; }
void set_val_box(int x, int y, int val, int weight) {
arr[m][81 * 3 + (get_box(x, y) - 1) * 9 + val] = weight; }
void set_val(int x, int y, int val) {
int weight = get_weight(x, y);
set_val_pos(x, y, weight);
set_val_row(y, val, weight);
set_val_col(x, val, weight);
set_val_box(x, y, val, weight); }
void print(void) {
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++)
if (arr[i][j]) printf("%d ", j);
printf("\n");
} printf("Matrix has %d rows, %d columns.\n", n, m); }
} mat;
class DancingLinksX
{
public:
struct node { node *l, *r, *u, *d; int v; };
node npool[40 * maxn], *head;
node *tmpidx[10 * maxn][maxn];
int ncnt;
node* make_node(void) {
node *p = &npool[ncnt++];
p->l = p->r = p->u = p->d = p;
return p; }
void init(Matrix m)
{
head = make_node();
// Making assistive nodes
node *last = head;
for (int i = 1; i <= m.n; i++) {
node *cur = make_node();
cur->l = last, last->r = cur;
tmpidx[0][i] = cur;
}
tmpidx[0][m.n]->r = head;
head->l = tmpidx[0][m.n];
// Rest are omitted, since they will always TLE.
}
} graph;
int n = 9; // Do not modify!
int arr[maxm][maxm];
int main(int argc, char** argv)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &arr[i][j]);
// Creating creation matrix
mat.n = 324, mat.m = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (arr[i][j] > 0) {
// Already set defined values
mat.new_row();
mat.set_val(j, i, arr[i][j]);
} else {
// Arbitrary values might occur here...
for (int k = 1; k <= 9; k++) {
mat.new_row();
mat.set_val(j, i, k);
}
}
// Made matrix, now preprocess matrix for Dancing Links X.
graph.init(mat);
mat.print();
return 0;
}然后就转战水暴力了.
于是有了这样的一个故事 (hs 分分钟 AC 掉了这道题), 但是我压位压了半天还是会崩, 所以 就直接写了数组.
但是这个数组常熟有点大 (雾), 在洛谷上交 75 分就不管了.
另外顺带说一句还有一种输出-1 的情况.
话说在交之前一直过不了样例数据, 一直输出 2112 左右的一个小数字 (并且特别慢). 后来才发现是有一个二维数组的地方没有写第二位, 而且 g++没有报错 (差评). 然后就调成差不多+1s 之内能过. 再然后发现答案还是不对, 就改了获得每一个位置的权的函数, 把一个 min 改成 max 然后就答案少了 400 左右. 最后是在无聊的时候自己造了这样一个数独出来玩:
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8很显然这个是对的是不是? 于是我就想挖掉一个空. 突然发现如果只挖掉一个空很可能只 输出这一个的权值, 然后就把其他的位置的权值都加上就可以了.
结果就这样的 75 分过了~
不是说了我不要剩下 25 分了么? 所以不要问我优化的问题.
Example Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long lli;
int get_box(int x, int y) { return (y <= 3 ? 1 : (y <= 6 ? 2 : 3)) * 3 - 3 + (x <= 3 ? 1 : (x <= 6 ? 2 : 3)); }
int get_weight(int x, int y) { return 10 - max(abs(y - 5), abs(x - 5)); }
class SodokuState
{
public:
bool state[28][10];
bool occupied[10][10];
inline void set_val(int x, int y, int val, bool dig) {
state[y][val] = !dig;
state[9 + x][val] = !dig;
state[18 + get_box(x, y)][val] = !dig;
occupied[y][x] = dig; }
inline bool get(int x, int y, int val) {
return state[y][val] && state[9 + x][val] && state[18 + get_box(x, y)][val]; }
inline void set(int x, int y, int val) { set_val(x, y, val, true); }
inline void unset(int x, int y, int val) { set_val(x, y, val, false); }
inline bool select_best(int &x, int &y) {
int best_val = 10;
for (int i = 1; i <= 9; i++)
for (int j = 1; j <= 9; j++) {
if (occupied[i][j]) continue;
int c_digits = 0;
for (int k = 1; k <= 9; k++)
c_digits += int(get(j, i, k));
if (c_digits < best_val && c_digits > 0)
x = j, y = i, best_val = c_digits;
}
if (best_val >= 10) return false;
return true; }
inline void clear(void) {
for (int i = 1; i <= 27; i++)
for (int j = 1; j <= 9; j++)
state[i][j] = true;
for (int i = 1; i <= 9; i++)
for (int j = 1; j <= 9; j++)
occupied[i][j] = false;
return ; }
inline bool empty(void) {
for (int i = 1; i <= 9; i++)
for (int j = 1; j <= 9; j++)
if (!occupied[i][j])
return false;
return true; }
};
int arr[10][10];
int dfs(SodokuState& ss, int depth, int score)
{
int final_res = 0;
#define maximize(__x) final_res = max(final_res, __x)
if (ss.empty())
return score;
// Checked intactness, selecting best node and look for it
int b_x = 1, b_y = 1;
if (!ss.select_best(b_x, b_y))
return 0;
for (int i = 1; i <= 9; i++)
if (ss.get(b_x, b_y, i)) {
ss.set(b_x, b_y, i);
maximize(dfs(ss, depth + 1, score + get_weight(b_x, b_y) * i));
ss.unset(b_x, b_y, i);
}
return final_res;
}
int main(int argc, char** argv)
{
for (int i = 1; i <= 9; i++)
for (int j = 1; j <= 9; j++)
scanf("%d", &arr[i][j]);
// Making initial state
SodokuState ss; ss.clear();
int t_res = 0;
for (int i = 1; i <= 9; i++)
for (int j = 1; j <= 9; j++)
if (arr[i][j]) {
ss.set(j, i, arr[i][j]);
t_res += arr[i][j] * get_weight(j, i);
}
// Searching
int res = dfs(ss, 0, 0);
if (!res)
printf("-1\n");
else
printf("%d\n", res + t_res);
return 0;
}