NOIP2009靶形数独

发表于 更新于 分类于 阅读次数：

Luogu P1074 靶形数独 题意为把数独填好并且按照指定方式求出最大的和
即必须枚举数独所有的解法 思路：dfs+剪枝 首先解数独，三个bool数组xx,yy,zz，xx[i][j]表示x=i时本行是否有j 然后我们可以知道，按照每一行0数量多少排序，从0最少的一行开始dfs可以减少搜索次数 于是就有了下面的AC代码

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
#define rint register int
using namespace std;

int a[10][10];
int w[10][10];
pair<int, int> tot[10];
int ord[15];
bool xx[10][10], yy[10][10], zz[10][10];
int ans = -1;
int x_now;
int x_final;

inline int get_z(int x, int y) {
    if (x <= 3) {
        if (y <= 3) return 1;
        if (y <= 6) return 2;
        else return 3;
    }
    else if (x <= 6) {
        if (y <= 3) return 4;
        if (y <= 6) return 5;
        else return 6;
    }
    else {
        if (y <= 3) return 7;
        if (y <= 6) return 8;
        else return 9;
    }
}

inline void get_ans() {
    rint sum = 0;
    for (rint i = 1; i <= 9; ++i) {
        for (rint j = 1; j <= 9; ++j) {
            sum += a[i][j] * w[i][j];
        }
    }
    ans = max(ans, sum);
}

inline void get_nxt(int &x, int &y) {
    if (y == 9) y = 1, x = ord[x];
    else ++y;
}

void dfs(int x, int y) {
    if (a[x][y]) {
        if (x == x_final && y == 9) {
            get_ans();
        }
        else {
            get_nxt(x, y);
            dfs(x, y);
        }
    }
    else {
        int xxx = x, yyy = y;
        get_nxt(xxx, yyy);
        for (rint i = 1; i <= 9; ++i) {
            if (xx[x][i]  yy[y][i]  zz[get_z(x, y)][i]) {
                continue;
            }
            xx[x][i] = yy[y][i] = zz[get_z(x, y)][i] = true;
            a[x][y] = i;
            if (x == x_final && y == 9) {
                get_ans();
            }
            else {
                dfs(xxx, yyy);
            }
            a[x][y] = 0;
            xx[x][i] = yy[y][i] = zz[get_z(x, y)][i] = false;
        }
    }
}

int main() {
    for (rint i = 1; i <= 9; ++i) {
        tot[i].second = i;
        for (rint j = 1; j <= 9; ++j) {
            scanf("%d", &a[i][j]);
            if (a[i][j] == 0) {
                ++tot[i].first;
            }
            else {
                xx[i][a[i][j]]
                    = yy[j][a[i][j]]
                    = zz[get_z(i, j)][a[i][j]]
                    = true;
            }
        }
    }
    for (rint i = 1; i <= 9; ++i) {
        for (rint j = 1; j <= 9; ++j) {
            rint t = min(min(i, 9 - i + 1), min(j, 9 - j + 1));
            if (t == 1) w[i][j] = 6;
            else if (t == 2) w[i][j] = 7;
            else if (t == 3) w[i][j] = 8;
            else if (t == 4) w[i][j] = 9;
            else if (t == 5) w[i][j] = 10;
        }
    }
    sort(tot + 1, tot + 10);
    for (rint i = 1; i <= 8; ++i) {
        ord[tot[i].second] = tot[i + 1].second;
    }
    x_now = tot[1].second;
    x_final = tot[9].second;
    dfs(x_now, 1);
    printf("%d", ans);
    return 0;
}