Accept: 444    Submit: 1365

Time Limit: 1000 mSec    Memory Limit : 32768 KB

解题思路：

题意为有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;

}