传送门FZU1686

【分析】和精确覆盖大致一样，只是删除的时候不需要删除选择行所覆盖的所有点的其他行，只要删除选中行覆盖的所有列即可，需要加上A*启发函数f()来强力剪枝，否则时间巨慢

【AC CODE】46ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 15*15+10, M = MAXN*MAXN;
/*和精确覆盖大致一样，只是删除的时候不需要删除选择行所覆盖的所有点的其他行，只要删除选中行覆盖的所有列即可
在找最小情况时，需要加上A*启发函数f()来强力剪枝，否则时间巨慢*/
struct DLX
{
private:
	int lt[M],rt[M],up[M],down[M],row[M],col[M],tol;
	int cnt[MAXN];
	void remove(int c)//删除列c所有元素
	{
		for(int i = down[c]; i != c; i = down[i])
			lt[rt[i]] = lt[i],rt[lt[i]] = rt[i],--cnt[col[i]];
	}
	void reset(int c)//恢复列c
	{
		for(int i = up[c]; i != c; i = up[i])
			lt[rt[i]] = rt[lt[i]] = i,++cnt[col[i]];
	}
	bool vis[MAXN];
	int f()//最少还需要几行才能覆盖
	{
		int ret = 0;
		for(int c = rt[0];c;c = rt[c]) vis[c] = true;
		for(int c = rt[0];c;c = rt[c])
		{
			if(vis[c])
			{
				ret++;
				vis[c] = false;
				for(int i = down[c]; i != c; i = down[i])
					for(int j = rt[i]; j != i; j = rt[j])
						vis[col[j]] = false;
			}
		}
		return ret;
	}
public:
	void init(int maxc)
	{
		repe(i,0,maxc)
			lt[i] = i-1,rt[i] = i+1,up[i] = down[i] = i;
		lt[0] = maxc,rt[maxc] = 0;
		tol = maxc+1;
		clc(cnt,0);
	}
	void add_row(int r,int len, int *a)
	{
		if(!len) return;
		int ft = tol;
		rep(i,0,len)
		{
			int c = a[i];
			row[tol] = r,col[tol] = c;
			lt[tol] = tol-1,rt[tol] = tol+1,up[tol] = up[c],down[tol] = c;
			down[up[c]] = tol, up[c] = tol;
			cnt[c]++,tol++;
		}
		lt[ft] = tol-1,rt[tol-1] = ft;
	}
	int mi;
	void dance(int d)
	{
		if(d+f() >= mi) return;//估价剪枝
		if(0 == rt[0])
		{
			if(mi > d) mi = d;
			return;
		}
		int c = rt[0];
		for(int i = rt[0];i;i = rt[i]) if(cnt[c] > cnt[i]) c = i;
		for(int i = down[c];i != c; i = down[i])//选择行row[i],并删除他所能覆盖的所有列
		{
			remove(i);
			for(int j = rt[i]; j != i; j = rt[j]) remove(j);//删除行row[i]能覆盖的所有列
			dance(d+1);
			for(int j = lt[i]; j != i; j = lt[j]) reset(j);
			reset(i);
		}
	}
}dlx;
int a[20][20],tmp[MAXN],num[20][20];
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n,m;
	while(~scanf("%d %d", &n, &m))
	{
		int sum = 0;
		rep(i,0,n)
		{
			rep(j,0,m)
			{
				scanf("%d", &a[i][j]);
				if(a[i][j])
					num[i][j] = ++sum;
			}
		}
		dlx.init(sum);
		int n1,m1,id = 0;
		scanf("%d %d",&n1, &m1);
		repe(i,0,n-n1)
		{
			repe(j,0,m-m1)
			{
				int ei = i+n1-1,ej = j+m1-1;
				int len = 0;
				repe(ii,i,ei)
				{
					repe(jj,j,ej)
					{
						if(a[ii][jj])
							tmp[len++] = num[ii][jj];
					}
				}
				dlx.add_row(++id,len,tmp);
			}
		}
		dlx.mi = INF;
		dlx.dance(0);
		printf("%d\n", dlx.mi);
	}
	return 0;
}