记录编号	600138	评测结果	AAAAAAAAATATAATTAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	80
用户昵称	wxs	是否通过	未通过
代码语言	C++	运行时间	10.683 s
提交时间	2025-04-16 20:20:50	内存使用	3.30 MiB

#include<bits/stdc++.h>
using namespace std;
const int n=20;
int ans=0;
int g[n][n],m=0;
int row[n][n],col[n][n],grid[5][5][n];
int score[20][20]={
	{6,6,6,6,6,6,6,6,6},
	{6,7,7,7,7,7,7,7,6},
	{6,7,8,8,8,8,8,7,6},
	{6,7,8,9,9,9,8,7,6},
	{6,7,8,9,10,9,8,7,6},
	{6,7,8,9,9,9,8,7,6},
	{6,7,8,8,8,8,8,7,6},
	{6,7,7,7,7,7,7,7,6},
	{6,6,6,6,6,6,6,6,6},
};
struct Node
{
    int x,y;
}a[1000];
bool dfs(int k,int t)
{
    if(k==m+1)
    {
        if(t<ans) return false;
        else{
            ans=t;
        }
    }
    int x=a[k].x,y=a[k].y;
    for(int num=1;num<=9;num++)
    {
        if(row[x][num]||col[y][num]||grid[x/3][y/3][num]) continue;
        g[x][y]=num;
        row[x][num]=col[y][num]=grid[x/3][y/3][num]=1;
        t+=score[x][y]*num;
        if(dfs(k+1,t)) return true;
        g[x][y]=0;
        row[x][num]=col[y][num]=grid[x/3][y/3][num]=0;
        t-=score[x][y]*num;
    }
    return false;
}
int main()
{
    freopen("sudoku.in","r",stdin);
    freopen("sudoku.out","w",stdout);
    
    m=0;
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            char op;
            cin>>op;
            op-='0';
            g[i][j]=op;
            if(op==0) a[++m]={i,j};
            row[i][op]=col[j][op]=grid[i/3][j/3][op]=1;
        }
    }
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++) ans+=score[i][j]*g[i][j];
    }
    int ans1=ans;
    dfs(1,ans1);
    //cout<<ans<<' '<<ans1<<endl;
    if(ans1!=ans) cout<<ans<<endl;
    else cout<<-1<<endl;
    return 0;
}