题解 P1074 【靶形数独 】

· · 题解

我一开始写这道题目的时候，感觉有点麻烦，然后就在网上搜了搜题解，发现好多人说细节特别多，还卡常，搞得我心慌慌的

后来发现这题其实贼简单，已经跟模拟差不多了，我感觉我的代码非常暴力，根本没啥优化，总用时1500ms，最慢的点300ms。

思路很简单，先处理出来每个格子能放哪几个数，如果只有一个数可以填，那就填上接着处理，

直到找不到能确定的格子，这时候找到一个候选数数量最少的格子，把几种情况都试一下，

然后继续填确定的格子，，如此反复。

代码中dfs1就是填所有确定的格子，dfs2就是选择候选数最少的格子

ZTs记录一个状态，fen表示分数

v表示某个格子填了哪个数

ok表示某个格子的某个数是否可选

sum表示某个格子有多少候选数

XY3数组是用来辅助处理小九宫格的，在jian1函数里用到

为什么叫jian1

这其实是个剪枝函数，本来我写了两个，第二个太繁琐，放弃了

第二个原理是，如果有两个格子，在同一行同一列或者同一个九宫格，他们的候选数都只有两个而且相同，那么其余7个方格肯定不会是这两个候选数。如果有三个格子候选数都是三个还相同，也是一样的道理，四个五个n个亦是如此，只是两个或三个的情况最常见，其余很少见

以下是代码

#include<stdio.h>
#include<string.h>
typedef struct ZTs
{
    int fen;
    char v[9][9];
    char ok[9][9][10];
    char sum[9][9];
}ZTs;
void dfs1(ZTs zt,int sh);
void dfs2(ZTs zt,int sh);
const int fen[9][9]=
{
    {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}
};
const int XY3[9]={0,0,0,3,3,3,6,6,6};
int map[9][9];
int ans=-1;
const int max(const int a,const int b)
{
    return a>b?a:b;
}
const int min(const int a,const int b)
{
    return a<b?a:b;
}
void m0(ZTs* zt)
{
    zt->fen=0;
    int i,j,k;
    for(i=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            zt->sum[i][j]=9;
            for(k=1;k<=9;k++)
            zt->ok[i][j][k]=1;
        }
    }
}
void jian1(ZTs* zt,const int x,const int y,const int z)
{
    int i,j,k,t;
    for(i=0;i<9;i++)
    {
        if(zt->ok[i][y][z])
        {
            zt->ok[i][y][z]=0;
            zt->sum[i][y]--;
        }
    }
    for(j=0;j<9;j++)
    {
        if(zt->ok[x][j][z])
        {
            zt->ok[x][j][z]=0;
            zt->sum[x][j]--;
        }
    }
    k=XY3[x]+3;
    t=XY3[y]+3;
    for(i=XY3[x];i<k;i++)
    for(j=XY3[y];j<t;j++)
    {
        if(zt->ok[i][j][z])
        {
            zt->ok[i][j][z]=0;
            zt->sum[i][j]--;
        }
    }
}
void dfs1(ZTs zt,int sh)
{
    if(sh==81)
    {
        ans=max(ans,zt.fen);
        return;
    }
    int i,j,k,b=0;
    for(i=0;i<9;i++)
    for(j=0;j<9;j++)
    {
        if(!zt.v[i][j])
        {
           if(zt.sum[i][j]==1)
           {
               b++;
               for(k=1;k<=9;k++)
               if(zt.ok[i][j][k])
               {
                   zt.fen+=k*fen[i][j];
                   zt.v[i][j]=k;
                   jian1(&zt,i,j,k);
                   break;
               }
           }
           else if(zt.sum[i][j]==0)
               return;
       }
    }
    if(b)dfs1(zt,sh+b);
    else dfs2(zt,sh);
}
void dfs2(ZTs zt,int sh)
{
    int i,j,mini,minj,minn=999;
    for(i=0;i<9;i++)
    for(j=0;j<9;j++)
    {
        if(!zt.v[i][j])
        {
            if(zt.sum[i][j]==0)return;
            if(zt.sum[i][j]<minn)
            {
                mini=i;
                minj=j;
                minn=zt.sum[i][j];
            }
        }
    }
    ZTs nzt;
    for(i=1;i<=9;i++)
    {
        if(zt.ok[mini][minj][i])
        {
            nzt=zt;
            nzt.fen+=i*fen[mini][minj];
            nzt.v[mini][minj]=i;
            jian1(&nzt,mini,minj,i);
            dfs1(nzt,sh+1);
        }
    }
}
int main()
{
    int i,j,k,sh=0;
    ZTs zt;
    for(i=0;i<9;i++)
    for(j=0;j<9;j++)
    scanf("%d",map[i]+j);
    m0(&zt);
    for(i=0;i<9;i++)
    for(j=0;j<9;j++)
    {
        if(map[i][j])sh++;
        zt.fen+=map[i][j]*fen[i][j];
        zt.v[i][j]=map[i][j];
    }
    for(i=0;i<9;i++)
    for(j=0;j<9;j++)
    if(zt.v[i][j])jian1(&zt,i,j,zt.v[i][j]);
    dfs1(zt,sh);
    printf("%d",ans);
}