fzu1686-神龙的难题

给出一个n\times m的01矩阵，以及\(h,w\)，表示一次可以把矩阵的一个\(h\times w\)的小矩阵变为全0，问至少要多少次可以把整个矩阵变为全0。\(n,m\le 15\)。

分析

注意到\(n,m\)非常小，我们可以直接暴力搜索。每次都可以把\(h\times w\)的小矩阵变为全0，那么贪心地想，同一个小矩阵肯定不会消两次。所以我们把每个原来为1的格子看成列，每一种覆盖看成行，那么这就是一个重复覆盖的问题。

重复覆盖问题一定要记得加剪枝。

代码

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<cstring>

using namespace std;

int read() {

	int x=0,f=1;

	char c=getchar();

	for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;

	for (;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*f;

}

const int maxn=17;

const int maxm=maxn*maxn;

const int maxp=maxm*maxm;

const int inf=1e9+7;

bool a[maxn][maxn];

int ids[maxn][maxn];

int ans,n,m;

int id(int x,int y) {

	return (x-1)*m+y;

}

struct node {

	int l,r,u,d,row,col;

};

struct DLX {

	node p[maxp];

	int tot,last[maxm],size[maxm];

	bool tic[maxm];

	void clear(int n) {

		memset(p,0,sizeof p),memset(last,0,sizeof last),memset(size,0,sizeof size),tot=n;

		p[0]=(node){n,1,0,0,0,0};

		for (int i=1;i<=n;++i) p[i]=(node){i-1,i+1,i,i,0,i},last[i]=i;

		p[n].r=0;

	}

	void build(int row,int a[],int len) {

		if (!len) return;

		p[++tot]=(node){tot,tot,last[a[1]],p[last[a[1]]].d,row,a[1]};

		p[p[tot].d].u=p[p[tot].u].d=last[a[1]]=tot;

		++size[p[tot].col];

		for (int i=2;i<=len;++i) {

			int x=a[i];

			p[++tot]=(node){tot-1,p[tot-1].r,last[x],p[last[x]].d,row,x};

			p[p[tot].d].u=p[p[tot].u].d=p[p[tot].l].r=p[p[tot].r].l=last[x]=tot;

			++size[p[tot].col];

		}

	}

	void del(int c) {

		for (int i=p[c].d;i!=c;i=p[i].d) p[p[i].l].r=p[i].r,p[p[i].r].l=p[i].l,--size[p[i].col];

	}

	void back(int c) {

		for (int i=p[c].u;i!=c;i=p[i].u) p[p[i].l].r=p[p[i].r].l=i,++size[p[i].col];

	}

	int est() {

		memset(tic,0,sizeof tic);

		int ret=0;

		for (int i=p[0].r;i;i=p[i].r) if (!tic[i]) {

			++ret;

			tic[i]=true;

			for (int j=p[i].d;j!=i;j=p[j].d) for (int k=p[j].r;k!=j;k=p[k].r) tic[p[k].col]=true;

		}

		return ret;

	}

	void dance(int now) {

		if (!p[0].r) {

			ans=min(ans,now);

			return;

		}

		if (now+est()>=ans) return;

		int first=p[0].r;

		for (int i=p[0].r;i;i=p[i].r) if (size[i]<size[first]) first=i;

		if (p[first].d==first) return;

		for (int i=p[first].d;i!=first;i=p[i].d) {

			del(i);

			for (int j=p[i].r;j!=i;j=p[j].r) del(j);

			dance(now+1);

			for (int j=p[i].l;j!=i;j=p[j].l) back(j);

			back(i);

		}

	}

} dlx;

int main() {

#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

	freopen("my.out","w",stdout);

#endif

	while (~scanf("%d%d",&n,&m)) {

		ans=inf;

		int ts=0;

		for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) {

			a[i][j]=read();

			if (a[i][j]) ids[i][j]=++ts;

		}

		dlx.clear(ts);

		int tn=read(),tm=read();

		for (int i=1;i<=n-tn+1;++i) for (int j=1;j<=m-tm+1;++j) {

			static int c[maxm];

			int tot=0;

			for (int x=i;x<i+tn;++x) for (int y=j;y<j+tm;++y) if (a[x][y]) c[++tot]=ids[x][y];

			dlx.build(id(i,j),c,tot);

		}

		dlx.dance(0);

		printf("%d\n",ans);

	}

	return 0;

}

巴特西

fzu1686-神龙的难题

分析

代码

最新文章

热门文章