[DLX精确覆盖+打表] hdu 2518 Dominoes

题意：

就是给12种图形，旋转，翻折。有多少种方法构成n*m=60的矩形

思路：

裸的精确覆盖。就是建图麻烦

个人太挫，直接手写每一个图形的各种形态

须要注意的是最后的答案须要除以4

代码：

#include"stdio.h"
#include"algorithm"
#include"string.h"
#include"iostream"
#include"queue"
#include"map"
#include"vector"
#include"string"
using namespace std;
/*int mp[63][5][5]=
{{//1.1{1,0,0},{1,0,0},{1,1,1},},{//1.2{1,1,1},{0,0,1},{0,0,1},},{//1.3{0,0,1},{0,0,1},{1,1,1},},{//1.4{1,1,1},{1,0,0},{1,0,0},},{//2.5{1,1,1,1,1},},{//2.6{1},{1},{1},{1},{1},},{//3.7{0,1,0},{1,1,1},{0,1,0},},{//4.8{1,1,1},{1,0,1},},{//4.9{1,0,1},{1,1,1},},{//4.10{1,1},{1,0},{1,1},},{//4.11{1,1},{0,1},{1,1},},{//5.12{1,1,1,1},{1,0,0,0},},{//5.13{1,0},{1,0},{1,0},{1,1},},{//5.14{0,0,0,1},{1,1,1,1},},{//5.15{1,1},{0,1},{0,1},{0,1},},{//5.16{1,0,0,0},{1,1,1,1},},{//5.17{0,1},{0,1},{0,1},{1,1},},{//5.18{1,1,1,1},{0,0,0,1},},{//5.19{1,1},{1,0},{1,0},{1,0},},{//6.20{1,0,0},{1,1,0},{0,1,1},},{//6.21{0,0,1},{0,1,1},{1,1,0},},{//6.22{1,1,0},{0,1,1},{0,0,1},},{//6.23{0,1,1},{1,1,0},{1,0,0},},{//7.24{1,1,1,1},{0,1,0,0},},{//7.25{1,0},{1,0},{1,1},{1,0},},{//7.26{0,0,1,0},{1,1,1,1},},{//7.27{0,1},{1,1},{0,1},{0,1},},{//7.28{0,1,0,0},{1,1,1,1},},{//7.29{0,1},{0,1},{1,1},{0,1},},{//7.30{1,1,1,1},{0,0,1,0},},{//7.31{1,0},{1,1},{1,0},{1,0},},{//8.32{0,0,1},{1,1,1},{1,0,0},},{//8.33{1,1,0},{0,1,0},{0,1,1},},{//8.34{1,0,0},{1,1,1},{0,0,1},},{//8.35{0,1,1},{0,1,0},{1,1,0},},{//9.36{0,1,0},{0,1,1},{1,1,0},},{//9.37{0,1,0},{1,1,1},{0,0,1},},{//9.38{0,1,1},{1,1,0},{0,1,0},},{//9.39{1,0,0},{1,1,1},{0,1,0},},{//9.40{1,1,0},{0,1,1},{0,1,0},},{//9.41{0,1,0},{1,1,1},{1,0,0},},{//9.42{0,1,0},{1,1,0},{0,1,1},},{//9.43{0,0,1},{1,1,1},{0,1,0},},{//10.44{0,1,0},{0,1,0},{1,1,1},},{//10.45{1,1,1},{0,1,0},{0,1,0},},{//10.46{0,0,1},{1,1,1},{0,0,1},},{//10.47{1,0,0},{1,1,1},{1,0,0},},{//11.48{0,1,1},{1,1,1},},{//11.49{1,1},{1,1},{0,1},},{//11.50{1,1,1},{1,1,0},},{//11.51{1,0},{1,1},{1,1},},{//11.52{1,1,1},{0,1,1},},{//11.53{1,1},{1,1},{1,0},},{//11.54{1,1,0},{1,1,1},},{//11.55{0,1},{1,1},{1,1},},{//12.56{0,1,1,1},{1,1,0,0},},{//12.57{1,0},{1,0},{1,1},{0,1},},{//12.58{0,0,1,1},{1,1,1,0},},{//12.59{1,0},{1,1},{0,1},{0,1},},{//12.60{1,1,1,0},{0,0,1,1},},{//12.61{0,1},{1,1},{1,0},{1,0},},{//12.62{1,1,0,0},{0,1,1,1},},{//12.63{0,1},{0,1},{1,1},{1,0},},
};
//a代表每一个的行，b代表每一个的列。c代表每一个属于哪种
int a[]= {3,3,3,3,1,5,3,2,2,3,3,2,4,2,4,2,4,2,4,3,3,3,3,2,4,2,4,2,4,2,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,3,2,3,2,3,2,3,2,4,2,4,2,4,2,4};
int b[]= {3,3,3,3,5,1,3,3,3,2,2,4,2,4,2,4,2,4,2,3,3,3,3,4,2,4,2,4,2,4,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,3,2,3,2,3,2,4,2,4,2,4,2,4,2};
int c[]= {1,1,1,1,2,2,3,4,4,4,4,5,5,5,5,5,5,5,5,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8,9,9,9,9,9,9,9,9,10,10,10,10,11,11,11,11,11,11,11,11,12,12,12,12,12,12,12,12};
#define N 63*66*(60+66+14)
#define M 63*66
int ooo,haha;
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; } void dance(int x) { if(R[0]==0 || R[0]>ooo) { haha++; //cnt=x; return ; } int now=R[0]; for(int i=R[0]; i!=0 && i<=ooo; i=R[i]) { if(S[i]m) swap(n,m); printf("%d\n",ans[n]); } return 0; }

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！