[ACM] FZU 1686 神龙的难题（DLX 反复覆盖）

Problem 1686 神龙的难题

Accept: 444 Submit: 1365

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

Source

FOJ月赛-2009年2月- TimeLoop

解题思路：

题意为有n*m的01矩阵，1代表有怪物。神龙的攻击范围为n1*m1的矩阵（感觉题目中没说清楚）,一次攻击能够把这个范围内的怪物所有消灭，问神龙最少攻击几次，把所有的怪物全都灭掉。

思路为：把原矩阵中的1编号，一共同拥有size个，那么建立新矩阵的列数就为size。由于原矩阵n*m，所以神龙每一次攻击攻击点一共同拥有n*m个。这里攻击点能够看作每一个攻击范围小矩阵的左上角那个点，由于攻击范围小矩阵最少是1*1, 也就是最多攻击n*m次。所以新矩阵的行数为n*m。也就是以攻击次数作为行。怪物的个数作为列。每一行上的1（每一次攻击）代表该攻击所能消灭的怪物。那么原问题也就转化为了构造出来的新矩阵中最少选多少行（发动几次攻击）, 这些行再组成的新矩阵中每一列至少有1个1 （由于要把全部的怪物都杀死，并且两次攻击的范围可能有重叠，一个怪物能够被两次攻击覆盖掉。也就是每列能够有多个1）。

代码：

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

const int maxn=250;

const int maxm=250;

const int maxnode=250*250;

int n,m,n1,m1;

int id[20][20];

struct DLX

{

    int n,m,size;

    int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];

    int H[maxn],S[maxn];

    int ansd,ans[maxn];

    void init(int _n,int _m)

    {

        n=_n;

        m=_m;

        for(int i=0;i<=m;i++)

        {

            S[i]=0;

            U[i]=D[i]=i;

            L[i]=i-1;

            R[i]=i+1;

        }

        R[m]=0,L[0]=m;

        size=m;

        for(int i=1;i<=n;i++)

            H[i]=-1;

    }

    void link(int r,int c)

    {

        ++S[Col[++size]=c];

        Row[size]=r;

        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;

        }

    }

    void remove(int c)

    {

        for(int i=D[c];i!=c;i=D[i])

            L[R[i]]=L[i],R[L[i]]=R[i];

    }

    void resume(int c)

    {

        for(int i=U[c];i!=c;i=U[i])

            L[R[i]]=R[L[i]]=i;

    }

    bool v[maxnode];

    int f()//精确覆盖区估算剪枝

    {

        int ret=0;

        for(int c=R[0];c!=0;c=R[c])

            v[c]=true;

        for(int c=R[0];c!=0;c=R[c])

            if(v[c])

        {

            ret++;

            v[c]=false;

            for(int i=D[c];i!=c;i=D[i])

                for(int j=R[i];j!=i;j=R[j])

                v[Col[j]]=false;

        }

        return ret;

    }

    void dance(int d)

    {

        if(d+f()>=ansd)//少了等号会超时

            return ;

        if(R[0]==0)

        {

            if(ansd>d)

                ansd=d;

            return ;

        }

        int c=R[0];

        for(int i=R[0];i!=0;i=R[i])

            if(S[i]<S[c])

            c=i;

        for(int i=D[c];i!=c;i=D[i])

        {

            remove(i);

            for(int j=R[i];j!=i;j=R[j])

                remove(j);

            dance(d+1);

            for(int j=L[i];j!=i;j=L[j])

                resume(j);

            resume(i);

        }

    }

};

DLX x;

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        int size=0;

        for(int i=1;i<=n;i++)

            for(int j=1;j<=m;j++)

        {

            scanf("%d",&id[i][j]);

            if(id[i][j])

            {

                id[i][j]=(++size);//为每一个怪物编号

            }

        }

        x.init(n*m,size);//一共同拥有size个1

        scanf("%d%d",&n1,&m1);

        size=1;

        for(int i=1;i<=n;i++)

            for(int j=1;j<=m;j++)

        {

            for(int ii=0;ii<n1&&i+ii<=n;ii++)//小矩阵攻击范围

                for(int jj=0;jj<m1&&j+jj<=m;jj++)

            {

                if(id[i+ii][j+jj])

                    x.link(size,id[i+ii][j+jj]);

            }

            size++;

        }

        x.ansd=0x3f3f3f3f;

        x.dance(0);

        printf("%d\n",x.ansd);

    }

    return 0;

}

神龙