zoj3209-Treasure Map

给出一个左下角为\((0,0)\)，右上角为\((n,m)\)的矩形，再给出\(k\)个在大矩形内的小矩形（可以重合），问是否能用这些小矩形完全覆盖这个大矩形，并且没有重合，如果可以至少需要多少个。

分析

看到覆盖和没有重合，就可以知道是精确覆盖问题。精确覆盖问题的经典数据结构Dancing Links用来优化X算法可以很高效地解决。

精确覆盖问题的重点在于转化成DLX能够处理的01矩阵精确覆盖。这个转化的一个有效的方法就是，找到什么东西不能重合，什么东西只能覆盖一次。

例如这个题中，说的是小矩形不能重合，事实上可以转化成每个格子只能被一个矩形覆盖，并且一定要覆盖。这样问题就简单了。我们建一个01矩阵，\(k\)行\(n\times m\)列，表示一个矩形能够覆盖哪些点。这样就可以直接用Dancing Links X解01精确覆盖的方法来解决了。

代码

这道题虽然简单，但又写了差不多一天。在一些acm网站上做题总是这样，都不知道哪里错了，不小心有AC了，又不知道怎么回事，好像之前Topcoder的愚人节比赛一样。不过还是找出原因了。

一个是在给点编号的时候，写的应该是\((x-1)*m+y\)，因为\(x\)是跟\(n\)有关的。还有一个就是，X算法本质上就是深搜的循环双向十字链表优化，所以该剪枝还是要剪枝，比如这里的最优性剪枝。

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

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=5e2+100;

const int maxm=1e3+100;

const int maxp=maxm*maxn;

const int inf=1e9+7;

bool a[maxn][maxm];

int n,m,ans;

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 last[maxm],tot,size[maxm];

	void clear(int cs) {

		memset(last,0,sizeof last);

		memset(size,0,sizeof size);

		memset(p,0,sizeof p);

		for (int i=1;i<=cs;++i) last[i]=i;

		tot=cs;

		for (int i=1;i<=cs;++i) {

			p[i]=(node){i-1,p[i-1].r,i,i,0,i};

			p[p[i].l].r=p[p[i].r].l=i;

		}

	}

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

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

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

		++size[c[1]];

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

			int x=c[i];

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

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

			++size[x];

		}

	}

	void del(int c) {

		p[p[c].l].r=p[c].r,p[p[c].r].l=p[c].l;

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

	}

	void back(int c) {

		p[p[c].l].r=p[p[c].r].l=c;

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

	}

	void dance(int k) {

		if (!p[0].r) {

			ans=min(ans,k);

			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;

		del(first);

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

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

			dance(k+1);

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

		}

		back(first);

	}

} dlx;

int main() {

#ifndef ONLINE_JUDGE

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

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

#endif

	int T=read();

	while (T--) {

		n=read(),m=read(),ans=inf;

		memset(a,0,sizeof a);

		int K=read();

		dlx.clear(n*m);

		for (int k=1;k<=K;++k) {

			int x1=read(),y1=read(),x2=read(),y2=read();

			for (int i=x1+1;i<=x2;++i) for (int j=y1+1;j<=y2;++j) a[k][id(i,j)]=true;

		}

		for (int i=1;i<=K;++i) {

			static int c[maxm];

			int tot=0;

			for (int j=1;j<=n*m;++j) if (a[i][j]) c[++tot]=j;

			dlx.build(i,c,tot);

		}

		dlx.dance(0);

		printf("%d\n",ans==inf?-1:ans);

	}

	return 0;

}

巴特西

zoj3209-Treasure Map

分析

代码

最新文章

热门文章