记录编号	580302	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	100
用户昵称	数声风笛ovo	是否通过	通过
代码语言	C++	运行时间	2.170 s
提交时间	2023-07-21 11:47:43	内存使用	3.44 MiB

#include <bits/stdc++.h>
using namespace std;
int ans = -1, a[10][10], b[10][10], c[10][10];
bool f1[10][10], f2[10][10], f3[10][10];
void dfs(int step)
{
    int i, j, k, s, xx, yy, zz = 10;
    for (i = 1; i <= 9; i++)
        for (j = 1; j <= 9; j++)
            if (a[i][j] == 0)
            {
                for (s = 0, k = 1; k <= 9; k++)
                {
                    if (!f1[c[i][j]][k] && !f2[i][k] && !f3[j][k])
                    {
                        s++;
                    }
                }
                if (s < zz)
                {
                    zz = s;
                    xx = i;
                    yy = j;
                }
            }
    if (zz == 10)
    {
        for (k = 0, i = 1; i <= 9; i++)
        {
            for (j = 1; j <= 9; j++)
            {
                k += a[i][j] * b[i][j];
            }
        }
        ans = max(ans, k);
        return;
    }
    if (zz == 0)
        return;
    for (k = 1; k <= 9; k++)
    {
        if (!f1[c[xx][yy]][k] && !f2[xx][k] && !f3[yy][k])
        {
            a[xx][yy] = k;
            f1[c[xx][yy]][k] = f2[xx][k] = f3[yy][k] = 1;
            dfs(step + 1);
            a[xx][yy] = 0;
            f1[c[xx][yy]][k] = f2[xx][k] = f3[yy][k] = 0;
        }
    }
    return;
}
int main()
{
    freopen("sudoku.in","r",stdin);
	freopen("sudoku.out","w",stdout); 
    int i, j;
    for (i = 1; i <= 9; i++)
    {
        for (j = 1; j <= 9; j++)
        {
            scanf("%d", &a[i][j]);
            b[i][j] = 10 - max(abs(i - 5), abs(j - 5));
            c[i][j] = (i - 1) / 3 * 3 + (j - 1) / 3 + 1;
            f1[c[i][j]][a[i][j]] = 1;
            f2[i][a[i][j]] = 1;
            f3[j][a[i][j]] = 1;
        }
    }
    dfs(1);
    printf("%d\n", ans);
    return 0;
}