洛谷1074 靶形数独

Luogu

算法

大力暴搜。

每次找到一个能填的数最少的格子,搜一搜即可。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

const int score[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},
};

int Map[20][20];
const int n=9;
bool row[10][10]; //row[i][j]表示第i行有无j
bool col[10][10]; //col[i][j]表示第i列有无j
bool area[10][10]; //area[i][j]表示第i宫有无j
int row_cnt[10],col_cnt[10];
int cnt=0,ans=-1;

inline int id(int X,int Y) { return (X-1)/3*3+1+(Y-1)/3; }
inline int Calc() {
    int rt=0;
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=n;j++)
            rt+=Map[i][j]*score[i][j];
    return rt;
}

inline void Dfs(int r,int c,int num) {
//    printf("%d %d %d\n",r,c,num);
    if (num==81) { ans=max(ans,Calc()); return; }
    for (re int i=1;i<=9;i++) {
        if (row[r][i]||col[c][i]||area[id(r,c)][i]) continue;
        row[r][i]=col[c][i]=area[id(r,c)][i]=1;
        row_cnt[r]++,col_cnt[c]++,Map[r][c]=i;
        int Maxr=-1,Maxc=-1,R,C;
        for (re int j=1;j<=n;j++)
            if (row_cnt[j]>Maxr&&row_cnt[j]<9) Maxr=row_cnt[j],R=j;
        for (re int j=1;j<=n;j++)
            if (col_cnt[j]>Maxc&&!Map[R][j]) Maxc=col_cnt[j],C=j;
        Dfs(R,C,num+1);
        row_cnt[r]--,col_cnt[c]--,Map[r][c]=0;
        row[r][i]=col[c][i]=area[id(r,c)][i]=0;
    }
}

int main() {
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=n;j++) {
            scanf("%d",&Map[i][j]);
            if (Map[i][j]) {
                row[i][Map[i][j]]=1;
                col[j][Map[i][j]]=1;
                area[id(i,j)][Map[i][j]]=1;
                row_cnt[i]++,col_cnt[j]++,cnt++;
            }
        }
    int Maxr=-1,Maxc=-1,r,c;
    for (re int i=1;i<=n;i++)
        if (row_cnt[i]>Maxr&&row_cnt[i]<9) Maxr=row_cnt[i],r=i;
    for (re int i=1;i<=n;i++)
        if (col_cnt[i]>Maxc&&!Map[r][i]) Maxc=col_cnt[i],c=i;
    Dfs(r,c,cnt);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 00 PM

发表评论