记录编号	543722	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	100
用户昵称	氢氦	是否通过	通过
代码语言	C++	运行时间	3.286 s
提交时间	2019-10-09 17:23:08	内存使用	13.82 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <bits/stdc++.h>
#define max(a, b) ((a) > (b) ? (a) : (b))

int ans, cnt, tot, mmp[100][100], belong[100][100], mark[100][100];
bool h[100][100], l[100][100], r[100][100];

struct Node {
    int num, sum;
    bool operator < (const Node & rhs) const {return sum < rhs.sum;}
}a[100];

struct E {
    int x, y, ma, be;
}kkk[1000];

void dfs(int p, int score) {
    //std::cout << p << '\n';
    if (p == cnt) {
        if (score > ans) ans = score;
        return ;
    }
    for (int i = 1; i <= 9; i++) {
        if (!h[kkk[p].x][i] && !l[kkk[p].y][i] && !r[kkk[p].be][i]) {
            h[kkk[p].x][i] = true, l[kkk[p].y][i] = true, r[kkk[p].be][i] = true;
            dfs(p + 1, score + (kkk[p].ma * i));
            h[kkk[p].x][i] = false, l[kkk[p].y][i] = false, r[kkk[p].be][i] = false;
        }
    }
}

int main() {
    freopen("sudoku.in", "r", stdin);
    freopen("sudoku.out", "w", stdout);
    for (int i = 1; i <= 9; i++) a[i].num = i;
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            if (i <= 3)
                if (j <= 3) belong[i][j] = 1; else if (j > 3 && j <= 6) belong[i][j] = 2; else belong[i][j] = 3;
            if (i > 3 && i <= 6)
                if (j <= 3) belong[i][j] = 4; else if (j > 3 && j <= 6) belong[i][j] = 5; else belong[i][j] = 6;
            if (i > 6 && i <= 9)
                if (j <= 3) belong[i][j] = 7; else if (j > 3 && j <= 6) belong[i][j] = 8; else belong[i][j] = 9;
        }
    }
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            if (i == 1 || j == 1 || i == 9 || j == 9) mark[i][j] = 6; mark[5][5] = 10;
            if ((i == 2 && j >= 2 && j <= 8) || (j == 2 && i >= 2 && i <= 8) || (i == 8 && j >= 2 && j <= 8) || (j == 8 && i >= 2 && i <= 8)) mark[i][j] = 7;
            if ((i == 3 && j >= 3 && j <= 7) || (j == 3 && i >= 3 && i <= 7) || (i == 7 && j >= 3 && j <= 7) || (j == 7 && i >= 3 && i <= 7)) mark[i][j] = 8;
            if ((i == 4 && j >= 4 && j <= 6) || (j == 4 && i >= 4 && i <= 6) || (i == 6 && j >= 4 && j <= 6) || (j == 6 && i >= 4 && i <= 6)) mark[i][j] = 9;
        }
    }
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++) {
            scanf("%d", &mmp[i][j]);
            if (mmp[i][j]) h[i][mmp[i][j]] = true, l[j][mmp[i][j]] = true, r[belong[i][j]][mmp[i][j]] = true, tot += mark[i][j] * mmp[i][j];
            if (!mmp[i][j]) a[i].sum++;
        }
    std::sort(a + 1, a + 10);
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            if (mmp[a[i].num][j] == 0) {
                    kkk[cnt].x = a[i].num, kkk[cnt].y = j, kkk[cnt].ma = mark[a[i].num][j], kkk[cnt++].be = belong[a[i].num][j];
            }
        }
    }
    //for (int i = 1; i <= cnt; i++) std::cout << kkk[i].x << ' ' << kkk[i].y << ' ' << kkk[i].ma << ' ' << kkk[i].be << '\n';
    dfs(0, tot);
    if (ans == 0) puts("-1");
    else printf("%d\n", ans);
    return 0;
}