Gym101252B-Kakuro题解

发表于 更新于 分类于

题目传送门

题意：有一个矩阵，每个格子为黑色或白色。你需要向白色格子中填 1∼91\sim 9 的整整睡。从某一个黑色格子的右侧往右连续的一段极长的白色格子被称为一个 run，往下连续一段同理。在每个 run 的开始位置会标记出该 run 的数字和。除此之外要求每个 run 内填的数互不相同。求一组合法解。n,m≤6n,m\le 6。

首先想到朴素的搜索，搜索每个格子填的数，在每个 run 的末尾进行一次 check。过程中维护 vis 和当前 run 填的数之和，进行可行性剪枝。这种做法显然无法通过此题。

首先考虑强化可行性剪枝。常规的可行性剪枝为，假设后面全填从 11 开始的连续数列也比目标大/后面全填从 99 开始的连续数列也比目标小，此时进行剪枝。但是这种是不够强的，因为没有考虑到当前 run 可能已经使用过一些元素，进行排除。所以由于数据非常小，可以预处理出 f[i][j][k]f[i][j][k] 表示当前能用的数字几何为 ii，还剩 jj 个格子待填，剩下的 jj 个格子能否填到 kk。这是一个不复杂的状压 DP，不再赘述。

然后就是非常重要的搜索顺序问题。显然每次我们希望找限制最强的位置搜索，具体地，先找限制最强的 run（尽快处理完），再在这个 run 内找限制最强的格子。前者可以通过维护每个 run 的数字使用情况 vis 和剩余格子 runleft 来计算，后者可以通过计算每个格子所在的两个 run 的 vis 的或来比较。这样看似在每次递归时都多消耗了复杂度来找限制最强的位置，但实际上这对效率的优化是及其显著的。

By cxm1024 From flydutchman

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<bits/stdc++.h>
using namespace std;
int n,m,cntrun=0,cntgrid=0;
int flag[10][10],dn[10][10],rt[10][10];
int run[60],lt[30],up[30],runleft[60];
pair<int,int> grid[30],lu[30];
int vis[60];
bool f[512][10][56],done[30];
int a[30];
void print() {
    int now=0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(flag[i][j]) cout<<"_ ";
            else cout<<a[++now]<<" ";
        }
        cout<<endl;
    }
    exit(0);
}
void dfs(int now) {
    if(now>cntgrid) {
        for(int i=1;i<=cntrun;i++)
            if(runleft[i]) return;
        print();
    }
    for(int i=1;i<=cntrun;i++)
        if(f[vis[i]^511][runleft[i]][run[i]]==0)
            return;
    int minx=10,minrun;
    for(int i=1;i<=cntrun;i++)
        if(run[i]!=0&&runleft[i]<minx)
            minx=runleft[i],minrun=i;
    int minn=10,mini;
    for(int i=1;i<=cntgrid;i++)
        if(!done[i]&&(lu[i].first==minrun||lu[i].second==minrun)) {
            int forb=vis[lu[i].first]|vis[lu[i].second];
            int tmp=9-__builtin_popcount(forb);
            if(tmp<minn)
                minn=tmp,mini=i;
        }
    done[mini]=1;
    for(int i=1;i<=9;i++) {
        if(vis[lu[mini].first]&(1<<(i-1))) continue;
        if(vis[lu[mini].second]&(1<<(i-1))) continue;
        vis[lu[mini].first]+=(1<<(i-1));
        vis[lu[mini].second]+=(1<<(i-1));
        runleft[lu[mini].first]--,runleft[lu[mini].second]--;
        run[lu[mini].first]-=i,run[lu[mini].second]-=i;
        a[mini]=i;
        if(f[vis[lu[mini].first]^511][runleft[lu[mini].first]][run[lu[mini].first]])
            if(f[vis[lu[mini].second]^511][runleft[lu[mini].second]][run[lu[mini].second]])
                dfs(now+1);
        vis[lu[mini].first]^=(1<<(i-1));
        vis[lu[mini].second]^=(1<<(i-1));
        runleft[lu[mini].first]++,runleft[lu[mini].second]++;
        run[lu[mini].first]+=i,run[lu[mini].second]+=i;
        a[mini]=0;
    }
    done[mini]=0;
}
signed main() {
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    for(int s=0;s<512;s++) {
        f[s][0][0]=1;
        for(int i=1;i<=9;i++) {
            if((s&(1<<(i-1)))==0) continue;
            for(int j=9;j>=0;j--)
                for(int k=0;k<=55;k++)
                    if(f[s][j][k])
                        f[s][j+1][k+i]=1;
        }
    }
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) {
            string s;
            cin>>s;
            if(s[2]=='.') {
                flag[i][j]=0;
                grid[++cntgrid]={i,j};
                rt[i][j]=rt[i][j-1];
                dn[i][j]=dn[i-1][j];
                lu[cntgrid]={dn[i][j],rt[i][j]};
                runleft[rt[i][j]]++;
                runleft[dn[i][j]]++;
            }
            else if(s[2]=='X')
                flag[i][j]=-1;
            else {
                flag[i][j]=1;
                if(s[0]!='X')
                    run[dn[i][j]=++cntrun]=(s[0]-'0')*10+s[1]-'0';
                if(s[3]!='X')
                    run[rt[i][j]=++cntrun]=(s[3]-'0')*10+s[4]-'0';
            }
        }
    dfs(1);
    return 0;
}