2011-08-16 12:06:47Morris
d780. NOIP2009 4.靶形数独
d780. NOIP2009 4.靶形数独
內容 ：
小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z博士请教，Z 博士拿出了他最近发明的“靶形数独” ，作为这两个孩子比试的题目。
靶 形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格高的小九宫格（用粗黑色线隔开的） 。在这个大九宫格中， 有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 1到 9 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列 也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。 （如图）
上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈（红色区域）每个格子为 9 分，再外面一圈（蓝色区域）每个格子为 8分，蓝色区域外面一圈（棕色区域）每个格子为 7分，最外面一圈（白色区域）每个格子为 6 分，如上图所示。
比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法） ，而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为 2829。游戏规定，将以总分数的高低决出胜负。
由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。
靶 形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格高的小九宫格（用粗黑色线隔开的） 。在这个大九宫格中， 有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 1到 9 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列 也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。 （如图）
上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈（红色区域）每个格子为 9 分，再外面一圈（蓝色区域）每个格子为 8分，蓝色区域外面一圈（棕色区域）每个格子为 7分，最外面一圈（白色区域）每个格子为 6 分，如上图所示。
比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法） ，而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为 2829。游戏规定，将以总分数的高低决出胜负。
由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。
輸入說明
：
一共 9 行。每行 9 个整数（每个数都在 0—9 的范围内） ，表示一个尚未填满的数独方格，未填的空格用“0”表示。每两个数字之间用一个空格隔开。
輸出說明
：
输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-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
提示
：
40%的数据，数独中非 0数的个数不少于 30。
80%的数据，数独中非 0数的个数不少于 26。
100%的数据，数独中非 0 数的个数不少于 24。
//其实本题有20个点，每个点的时限为2s。
//由于zerojudge的时间限制最大只能是1s，所以我只把能够在1s内的测试数据提交，并且只提交了10个点。
//官方测试数据中，其实只有第17点和第20点很难在1s内通过，因此在此略去。
//其实是因为zerojudge的评测系统不够快，他们在一些更快的评测系统的OJ上是可以在1s内通过的！
//以下给出第17点的测试数据，供大家钻研到能在1s内通过：
Sample input:
0 0 0 9 0 0 0 0 0
7 0 0 2 0 0 0 0 0
5 2 0 8 0 0 0 0 0
6 0 0 7 0 2 0 3 4
2 0 0 0 0 0 0 0 7
3 7 4 0 0 0 0 0 5
9 0 2 4 1 0 0 7 0
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 9 0 0
Sample output:
2856
出處
：
/**********************************************************************************/
/* Problem: d780 "NOIP2009 4.靶形数独" from NOIP2009提高组第四题 */
/* Language: C */
/* Result: AC (49ms, 293KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-16 11:46:27 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define Maxv 100000
struct DacingLinks {
int left, right;
int up, down;
int data, ch, rh;
}DL[100001 + 1001];
int s[1001], o[1001], head, size;
int n, m, a, b, c, tn, Ans;
int Score[10][10]={
{6,6,6,6, 6,6,6,6,6},
{6,7,7,7, 7,7,7,7,6},
{6,7,8,8, 8,8,8,7,6},
{6,7,8,9, 9,9,8,7,6},
{6,7,8,9,10,9,8,7,6},
{6,7,8,9, 9,9,8,7,6},
{6,7,8,8, 8,8,8,7,6},
{6,7,7,7, 7,7,7,7,6},
{6,6,6,6, 6,6,6,6,6},
};
void Remove(int c) {
DL[DL[c].right].left = DL[c].left;
DL[DL[c].left].right = DL[c].right;
int i, j;
for(i = DL[c].down; i != c; i = DL[i].down) {
for(j = DL[i].right; j != i; j = DL[j].right) {
DL[DL[j].down].up = DL[j].up;
DL[DL[j].up].down = DL[j].down;
s[DL[j].ch]--;
}
}
}
void Resume(int c) {
int i, j;
for(i = DL[c].down; i != c; i = DL[i].down) {
for(j = DL[i].left; j != i; j = DL[j].left) {
DL[DL[j].down].up = j;
DL[DL[j].up].down = j;
s[DL[j].ch]++;
}
}
DL[DL[c].right].left = c;
DL[DL[c].left].right = c;
}
void board(int k) {
static int set[81], a, b;
int sum = 0;
for(a = 0; a < k; a++) {
set[DL[o[a]].data] = DL[o[a]].rh+1;
}
for(a = 0; a < n; a++) {
for(b = 0; b < n; b++) {
sum += Score[a][b]*set[a*n+b];
}
}
Ans = Ans > sum ? Ans : sum;
}
void DFS(int k) {
if(DL[head].right == head) {
board(k);
return;
}
int t = Maxv, c, i, j;
for(i = DL[head].right; i != head; i = DL[i].right) {
if(s[i] < t) {
t = s[i], c = i;
}
}
Remove(c);
for(i = DL[c].down; i != c; i = DL[i].down) {
o[k] = i;
for(j = DL[i].right; j != i; j = DL[j].right)
Remove(DL[j].ch);
DFS(k+1);
for(j = DL[i].left; j != i; j = DL[j].left)
Resume(DL[j].ch);
}
Resume(c);
}
int new_node(int up, int down, int left, int right) {
DL[size].up = up, DL[size].down = down;
DL[size].left = left, DL[size].right = right;
DL[up].down = DL[down].up = DL[left].right = DL[right].left = size;
return size++;
}
void new_row(int n, int Row[], int rh, int set) {
int a, r, row = -1, k;
for(a = 0; a < n; a++) {
r = Row[a];
DL[size].ch = r, DL[size].data = set, s[r]++;
if(row == -1) {
row = new_node(DL[DL[r].ch].up, DL[r].ch, size, size);
DL[row].rh = rh;
}else {
k = new_node(DL[DL[r].ch].up, DL[r].ch, DL[row].left, row);
DL[k].rh = rh;
}
}
}
void init(int m) {
size = 0;
head = new_node(0, 0, 0, 0);
int i;
for(i = 1; i <= m; i++) {
new_node(i, i, DL[head].left, head);
DL[i].ch = i, s[i] = 0;
}
}
main() {
int map[10][10], Row[10], t;
n = 3;
tn = n, n *= n, m = n*n*4, init(m);
for(a = 0; a < n; a++)
for(b = 0; b < n; b++) {
scanf("%d", &map[a][b]);
if(map[a][b] == 0) {
for(c = 0; c < n; c++) {
t = 0;
Row[t++] = a*n + b + 1;
Row[t++] = n*n + a*n + c + 1;
Row[t++] = 2*n*n+ b*n + c + 1;
Row[t++] = 3*n*n+ (a/tn*tn + b/tn)*n + c + 1;
new_row(t, Row, c, a*n+b);
}
} else {
c = map[a][b]-1, t = 0;
Row[t++] = a*n + b + 1;
Row[t++] = n*n + a*n + c + 1;
Row[t++] = 2*n*n+ b*n + c + 1;
Row[t++] = 3*n*n+ (a/tn*tn + b/tn)*n + c + 1;
new_row(t, Row, c, a*n+b);
}
}
Ans = 0, DFS(0);
printf("%d\n", Ans);
return 0;
}
上一篇：b058. 3. 關鍵邏輯閘