靶形数独

https://www.luogu.org/problemnew/show/P1074

题解：

DFS

需要先搜索最少未填数的一行；

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
typedef __int128 lll;
const int N=10000;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,q;
ll ans=-1;
struct node {
    int lx , sum ;
}line[ 11 ] ;//记录每行需要填的零的个数;
bool cmp( node i , node j ) {
    return i.sum > j.sum ;
}
int a[10][10];
int b[10][10];
int c[10][10]={
    {0,0,0,0,0,0,0,0,0,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},
};
bool row[10][10];
bool col[10][10];
bool block[10][10];
void dfs(int id,int x,int y,ll cnt){
    if(id==9&&y==9){
//        for(int i=1;i<=9;i++){
//            for(int j=1;j<=9;j++){
//
//                cout << a[i][j]<< " ";
//            }
//            cout << endl;
//        }
//        cout <<"-----------------"<< cnt<< endl;
        ans=max(cnt,ans);
        return;
    }
    if(y==9){
        y=1;
        x=line[++id].lx;
    }else{
        y++;
    }
    if(!a[x][y]){
        for(int i=1;i<=9;i++){
            if(!row[x][i]&&!col[y][i]&&!block[b[x][y]][i]){
                row[x][i]=1;
                col[y][i]=1;
                block[b[x][y]][i]=1;
                a[x][y]=i;
                dfs(id,x,y,cnt+i*c[x][y]);
                a[x][y]=0;
                row[x][i]=0;
                col[y][i]=0;
                block[b[x][y]][i]=0;
            }
        }

    }else{
         dfs(id,x,y,cnt+a[x][y]*c[x][y]);
    }


}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //scanf("%d",&n);
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            t=(i-1)*3+j;
            int r=(i-1)*3;
            int c=(j-1)*3;
            for(int k=1;k<=3;k++){
                for(int l=1;l<=3;l++){
                    b[r+k][c+l]=t;
                }
            }
        }
    }
    for(int i=1;i<=9;i++){
        line[i].lx=i;
        line[i].sum=0;
        for(int j=1;j<=9;j++){
            scanf("%d",&a[i][j]);
            if(a[i][j]){
                line[i].sum++;
                row[i][a[i][j]]=1;
                col[j][a[i][j]]=1;
                block[b[i][j]][a[i][j]]=1;
            }
        }
        //cout << endl;
    }
    sort( line + 1 , line+ 10 , cmp );
    dfs(1,line[1].lx,0,0);
    cout << ans << endl;

    //cout << "Hello world!" << endl;
    return 0;
}