fzu 1686(Dancing Links 重复覆盖)_dancing link 精确覆盖重复覆盖 (dlx) python-CSDN博客

本文链接：https://blog.csdn.net/fp_hzq/article/details/6795027

在一个充满剑与魔法的世界里，艾米莉与她的神龙米格拉共同面对城市附近的魔物威胁，通过时间停止魔法，他们计划以最高效的方式消灭所有魔物，减轻艾米莉的负担。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Problem 1686 神龙的难题

Accept: 224 Submit: 801
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

这是个剑与魔法的世界.英雄和魔物同在,动荡和安定并存.但总的来说,库尔特王国是个安宁的国家,人民安居乐业,魔物也比较少.但是.总有一些魔物不时会进入城市附近,干扰人民的生活.就要有一些人出来守护居民们不被魔物侵害.魔法使艾米莉就是这样的一个人.她骑着她的坐骑,神龙米格拉一起消灭干扰人类生存的魔物,维护王国的安定.艾米莉希望能够在损伤最小的前提下完成任务.每次战斗前,她都用时间停止魔法停住时间,然后米格拉他就可以发出火球烧死敌人.米格拉想知道,他如何以最快的速度消灭敌人,减轻艾米莉的负担.

Input

数据有多组,你要处理到EOF为止.每组数据第一行有两个数,n,m,(1<=n,m<=15)表示这次任务的地区范围. 然后接下来有n行,每行m个整数,如为1表示该点有怪物,为0表示该点无怪物.然后接下一行有两个整数,n1,m1 (n1<=n,m1<=m)分别表示米格拉一次能攻击的行,列数(行列不能互换),假设米格拉一单位时间能发出一个火球,所有怪物都可一击必杀.

Output

输出一行,一个整数,表示米格拉消灭所有魔物的最短时间.

Sample Input

   4 41 0 0 10 1 1 00 1 1 01 0 0 12 24 4 0 0 0 00 1 1 00 1 1 00 0 0 02 2 
 

Sample Output

41

Source

FOJ月赛-2009年2月- TimeLoop

题目： http://acm.fzu.edu.cn/problem.php?pid=1686

分析：给每个魔物标号，枚举每一种攻击方式，现在就是要求选择最少的攻击方式，使得所有魔物都被至少攻击一次，于是就是DLX的重复覆盖问题了，直接敲模板。。。

为什么我的模板老是那么慢，难道是构图的部分影响？？主题部分和其他人没有差距阿？？

代码：

#include<cstdio>
#define mm 55555
#define mn 333
int U[mm],D[mm],L[mm],R[mm],C[mm];
int H[mn],S[mn],id[22][22];
bool v[mn];
int n,m,size,ans;
void prepare(int r,int c)
{
    for(int i=0;i<=c;++i)
    {
        S[i]=0;
        D[i]=U[i]=i;
        L[i+1]=i;
        R[i]=i+1;
    }
    R[c]=0;
    while(r)H[r--]=-1;
}
int f()
{
    int i,j,c,ret=0;
    for(c=R[0];c;c=R[c])v[c]=1;
    for(c=R[0];c;c=R[c])
        if(v[c])for(v[c]=0,++ret,i=D[c];i!=c;i=D[i])
            for(j=R[i];j!=i;j=R[j])v[C[j]]=0;
    return ret;
}
void remove(int c)
{
    for(int i=D[c];i!=c;i=D[i])
        R[L[i]]=R[i],L[R[i]]=L[i];
}
void resume(int c)
{
    for(int i=U[c];i!=c;i=U[i])
        R[L[i]]=L[R[i]]=i;
}
void Dance(int k)
{
    if(k+f()>=ans)return;
    if(!R[0])
    {
        ans=k;
        return;
    }
    int i,j,c,tmp=mm;
    for(i=R[0];i;i=R[i])
        if(S[i]<tmp)tmp=S[c=i];
    for(i=D[c];i!=c;i=D[i])
    {
        remove(i);
        for(j=R[i];j!=i;j=R[j])remove(j);
        Dance(k+1);
        for(j=L[i];j!=i;j=L[j])resume(j);
        resume(i);
    }
}
void Link(int r,int c)
{
    ++S[C[++size]=c];
    D[size]=D[c];
    U[D[c]]=size;
    U[size]=c;
    D[c]=size;
    if(H[r]<0)H[r]=L[size]=R[size]=size;
    else
    {
        R[size]=R[H[r]];
        L[R[H[r]]]=size;
        L[size]=H[r];
        R[H[r]]=size;
    }
}
int main()
{
    int i,j,k,l,mr,mc,r;
    while(scanf("%d%d",&n,&m)!=-1)
    {
        for(size=0,i=1;i<=n;++i)
            for(j=1;j<=m;++j)
            {
                scanf("%d",&k);
                id[i][j]=(k)?++size:0;
            }
        scanf("%d%d",&mr,&mc);
        prepare(n*m,size);
        for(i=r=1;i<=n-mr+1;++i)
            for(j=1;j<=m-mc+1;++j,++r)
                for(k=i;k<i+mr;++k)
                    for(l=j;l<j+mc;++l)
                        if(id[k][l])Link(r,id[k][l]);
        ans=n*m;
        Dance(0);
        printf("%d\n",ans);
    }
    return 0;
}