VIJOS1755 - [NOIP2009]靶形数独

2016/10/18

一道很吼的搜索,有人推荐做。主要是状态的表示。

(条件编译大法好!

题目描述

小城和小华都是热爱数学的好学生,最近,他们不约而同地迷上了数独游戏,好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了,于是他们向 Z博士请教,Z 博士拿出了他最近发明的“靶形数独” ,作为这两个孩子比试的题目。 靶形数独的方格同普通数独一样,在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格高的小九宫格(用粗黑色线隔开的) 。在这个大九宫格中,有一些数字是已知的,根据这些数字,利用逻辑推理,在其他的空格上填入 1到 9 的数字。每个数字在每个小九宫格内不能重复出现,每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同,即每一个方格都有一个分值,而且如同一个靶子一样,离中心越近则分值越高。 由于求胜心切,小城找到了善于编程的你,让你帮他求出,对于给定的靶形数独,能够得到的最高分数。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
#define matt(x, y) (((x)-1)/3*3+((y)-1)/3+1)     // 蜜汁压位
#define searchnext(x,y) y == 9 ? search(x+1, 1) : search(x, y+1)
#ifndef LCYTEST
#   define release(_x) { _x }
#else
#   define release(_x) ;
#endif
bool r[10][10], l[10][10], s[10][10];
int mata[10][10], b[10][10];
int ans = -1, score;

int getscore(int x, int y, int k) {
    if(x == 5 && y == 5) { return 10*k; }
    else if(x >= 4 && x <= 6 && y >= 4 && y <= 6) { return 9*k; }
    else if(x >= 3 && x <= 7 && y >= 3 && y <= 7) { return 8*k; }
    else if(x >= 2 && x <= 8 && y >= 2 && y <= 8) { return 7*k; }
    else { return 6*k; }
}

bool fill(int x, int y, int k) {
    if(r[x][k]) return 0;
    if(l[y][k]) return 0;
    if(s[matt(x, y)][k]) return 0;
    b[x][y] = k;
    r[x][k] = l[y][k] = s[matt(x, y)][k] = 1;
    score += getscore(x, y, k);
    return 1;
}

void del(int x, int y, int k) {
    b[x][y] = 0; r[x][k] = l[y][k] = s[matt(x, y)][k] = 0;
}

void search(int x, int y) {
    release({ if(clock() > 900) return; })
    if(x == 10 && y == 1) { ans = max(ans, score); return; }
    if(b[x][y]) searchnext(x,y);
    else
        for(int i=1;i<=9;i++) {
            int t=score;
            if(fill(x, y, i)) {
                searchnext(x, y);
                del(x, y, i);
                score=t;
            }
        }
}

int main() {
    release({ ios::sync_with_stdio(false); cin.tie(nullptr); })
    for(int i=9;i>0;i--)
        for(int j=9;j>0;j--) {
            cin >> mata[i][j];
            if(mata[i][j]) fill(i, j, mata[i][j]);
        }
    
    search(1, 1);
    cout << ans << endl;
}