记录编号	42414	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	1.823 s
提交时间	2012-09-23 14:22:17	内存使用	0.29 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 10;
const int w[N][N] = {{0},
    {0,6,6,6,6, 6,6,6,6,6},
    {0,6,7,7,7, 7,7,7,7,6},
    {0,6,7,8,8, 8,8,8,7,6},
    {0,6,7,8,9, 9,9,8,7,6},
    {0,6,7,8,9,10,9,8,7,6},
    {0,6,7,8,9, 9,9,8,7,6},
    {0,6,7,8,8, 8,8,8,7,6},
    {0,6,7,7,7, 7,7,7,7,6},
    {0,6,6,6,6, 6,6,6,6,6}};
const int v[N][N] = {{0},
    {0,1,1,1,2,2,2,3,3,3},
    {0,1,1,1,2,2,2,3,3,3},
    {0,1,1,1,2,2,2,3,3,3},
    {0,4,4,4,5,5,5,6,6,6},
    {0,4,4,4,5,5,5,6,6,6},
    {0,4,4,4,5,5,5,6,6,6},
    {0,7,7,7,8,8,8,9,9,9},
    {0,7,7,7,8,8,8,9,9,9},
    {0,7,7,7,8,8,8,9,9,9}};
int G[N][N], k[N*N][2];
bool h[N][N], r[N][N], b[N][N];
int x, t, s, n, d;
void DFS(int d, int m) {
    if(n++ > 10000000) return;
    if(!d) { s = max(s, m); return; }
    int i = k[d][0], j = k[d][1];
    for(int l=1; l<=9; l++)
        if(!h[i][l] && !r[j][l] && !b[v[i][j]][l]) {
            h[i][l] = r[j][l] = b[v[i][j]][l] = 1;
            DFS(d - 1, m + l * w[i][j]);
            h[i][l] = r[j][l] = b[v[i][j]][l] = 0;
        }
}
int main() {
    freopen("sudoku.in", "r", stdin);
    freopen("sudoku.out", "w", stdout);
    for(int i=1; i<=9; i++)
        for(int j=1; j<=9; j++) {
            scanf("%d", &x);
            if((G[i][j] = x)) {
                h[i][x] = r[j][x] = b[v[i][j]][x] = 1;
                t += x * w[i][j];
            } else {
                d++;
                k[d][0] = i; k[d][1] = j;
            }
        }
    DFS(d, t);
    printf("%d\n", s ? s : -1);
    return 0;
}