[NOIP 2009]靶形数独题解

题目链接：点击

题目的一些信息就不给了，点链接吧。

解题思路：

我总结为一个要点，一个优化：

要点：搜索顺序不能

for(i=1;i<=9;i++)

for(j=1;j<=9;j++)

这样时间复杂度过不去。

如何搜索？

当做填数字一样，每一个格子枚举数组，从上到下，从左到右填过去。

优化：这真的是欺负我这种没有玩过数独的人。

从已经填数字多的一行填，对行排个序，虽然每个格子都要填，这样每个格子能够搜索的状态数总体变少了，就行了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define R register int 
#define L inline int
using namespace std;
const int N=10;
int a[N][N],line[N][N],list[N][N],nine[N][N];
int ans,flag,ned,cnt;
struct T{
    int p,w;
}o[N*N];
bool cmp(T qq,T ee){
    return qq.w>ee.w;
}
L judge(R x,R y){
    if(x<=3){
        if(y<=3)return 1;
        if(y>=7)return 3;
        return 2;
    }
    if(x<=6&&x>=4){
        if(y<=3)return 4;
        if(y>=7)return 6;
        return 5;
    }
    else
    {
        if(y<=3)return 7;
        if(y>=7)return 9;
        return 8;
    }
}
L pd(R x,R y){
    if(x==1||y==1||x==9||y==9)return 6;
    if(x==2||y==2||x==8||y==8)return 7;
    if(x==3||y==3||x==7||y==7)return 8;
    if(x==4||y==4||x==6||y==6)return 9;
    return 10;
}
inline void dfs(R num,R tot,R x,R y){
    if(num==81){
    flag=1;
    ans=max(tot,ans);
    return;
    }
    if(y==10)
    dfs(num,tot,x+1,1);
    else
    if(a[o[x].p][y])
    dfs(num,tot,x,y+1);
    else
    {
        R root=judge(o[x].p,y);
    for(R i=1;i<=9;++i){
        if(!line[o[x].p][i]&&!list[y][i]&&!nine[root][i]){
           line[o[x].p][i]=list[y][i]=nine[root][i]=1;
           if(num==81){
           flag=1;
           ans=max(tot,ans);
           line[o[x].p][i]=list[y][i]=nine[root][i]=0;
           return;
          }
           dfs(num+1,tot+i*pd(o[x].p,y),x,y+1);
           line[o[x].p][i]=list[y][i]=nine[root][i]=0;
        }
    }
    }
}
int main(){
    for(R i=1;i<=9;++i)
    for(R j=1;j<=9;++j){
    o[i].p=i;
    scanf("%d",&a[i][j]);
    if(a[i][j]){
    cnt++;
    o[i].w++;
    ans+=pd(i,j)*a[i][j];
    line[i][a[i][j]]=1;
    list[j][a[i][j]]=1;
    nine[judge(i,j)][a[i][j]]=1;
    }
    }
    sort(o+1,o+9+1,cmp);
    ned=ans;
    dfs(cnt,ned,1,1);
    if(!flag)
    printf("-1");
    else
    printf("%d",ans);
    return 0;
}