[DLX精确覆盖] hdu 1603 A Puzzling Problem

[DLX精确覆盖] hdu 1603 A Puzzling Problem

题意：

给你n块碎片，这些碎片不能旋转、翻折。

问你能不能用当中的某些块拼出4*4的正方形。

思路：

精确覆盖裸题了

建图就是看看每一个碎片在4*4中能放哪些位置，这个就作为行。

列就是4*4=16个位置再加上n个碎片也就是16+n

然后注意下成立的判定就好了

代码：

#include"stdio.h"
#include"algorithm"
#include"string.h"
#include"iostream"
#include"queue"
#include"map"
#include"vector"
#include"string"
using namespace std;
#define N 1005*1005
#define RN 1005
#define M 1005
struct DLX
{int n,m,C;int U[N],D[N],L[N],R[N],Row[N],Col[N];int H[M],S[M],cnt,ans[M];void init(int _n,int _m){n=_n;m=_m;for(int i=0; i<=m; i++){U[i]=D[i]=i;L[i]=(i==0?m:i-1);R[i]=(i==m?0:i+1);S[i]=0;}C=m;for(int i=1; i<=n; i++) H[i]=-1;}void link(int x,int y){C++;Row[C]=x;Col[C]=y;S[y]++;U[C]=U[y];D[C]=y;D[U[y]]=C;U[y]=C;if(H[x]==-1) H[x]=L[C]=R[C]=C;else{L[C]=L[H[x]];R[C]=H[x];R[L[H[x]]]=C;L[H[x]]=C;}}void del(int x){R[L[x]]=R[x];L[R[x]]=L[x];for(int i=D[x]; i!=x; i=D[i]){for(int j=R[i]; j!=i; j=R[j]){U[D[j]]=U[j];D[U[j]]=D[j];S[Col[j]]--;}}}void rec(int x){for(int i=U[x]; i!=x; i=U[i]){for(int j=L[i]; j!=i; j=L[j]){U[D[j]]=j;D[U[j]]=j;S[Col[j]]++;}}R[L[x]]=x;L[R[x]]=x;}int dance(int x){if(R[0]==0 || R[0]>16){cnt=x;return 1;}int now=R[0];for(int i=R[0]; i!=0 && i<=16; i=R[i]){if(S[i]<S[now]) now=i;}del(now);for(int i=D[now]; i!=now; i=D[i]){ans[x]=Row[i];for(int j=R[i]; j!=i; j=R[j]) del(Col[j]);if(dance(x+1)) return 1;for(int j=L[i]; j!=i; j=L[j]) rec(Col[j]);}rec(now);return 0;}
} dlx;
struct node
{int m,id;int w[44];
} kx[1234];
int main()
{int n;while(scanf("%d",&n),n){int cnt=0;dlx.init(n*16,16+n);for(int i=1; i<=n; i++){int a,b;scanf("%d%d",&a,&b);char v[12][12];for(int j=0; j<a; j++) scanf("%s",v[j]);for(int xx=1; xx+a<=5; xx++){for(int yy=1; yy+b<=5; yy++){cnt++;kx[cnt].m=0;kx[cnt].id=i;for(int x=0; x<a; x++){for(int y=0; y<b; y++){if(v[x][y]=='1'){int tep=(xx+x-1)*4+(yy+y);dlx.link(cnt,tep);kx[cnt].w[kx[cnt].m++]=tep;}}}dlx.link(cnt,16+i);}}}int f=dlx.dance(0);if(f==0) puts("No solution possible");else{char mp[10][10];for(int i=0;i<dlxt;i++){for(int j=0;j<kx[dlx.ans[i]].m;j++){int x,y;x=(kx[dlx.ans[i]].w[j]-1)/4;y=kx[dlx.ans[i]].w[j]%4-1;if(y==-1) y=3;mp[x][y]=kx[dlx.ans[i]].id+'0';}}for(int i=0;i<4;i++){mp[i][4]='';puts(mp[i]);}}puts("");}return 0;
}

转载于:.html