首页 > 代码库 > SGU 131.Hardwood floor

SGU 131.Hardwood floor

2024-07-11 10:06:19   220人阅读

时间限制：0.25s

空间限制：4M

 

题意：

       给出 n*m (1≤n、m≤9)的方格棋盘，用 1*2 的矩形的骨牌和 L 形的(2*2 的

去掉一个角)骨牌不重叠地覆盖，求覆盖满的方案数。

 

 

 

Solution：

             还是状态压缩，这次的情况比较多，要全部列出。

             b1，b2分别代表上下两行前列对下一列的影响

             s1,s2对应上下两行的状态

         情况

上列b1，b2要求

状态改变对下一列的影响

10

10

b1=0,

b2=0;

s1<<1,

s2<<1|1;

b1=0,

b2=0;

11

10

b1=0,

b2=0;

s1<<1,

s2<<1|1;

b1=1,

b2=0;

10

11

b1=0,

b2=0;

s1<<1,

s2<<1|1;

b1=0,

b2=1;

00

11

b2=0;

s1<<1|1-b1,

s2<<1|1;

b1=0,

b2=1;

01

11

b2=0;

s1<<1|1-b1,

s2<<1|1;

b1=1,

b2=1;

11

01

b1=0;

s1<<1,

s2<<1|b2;

b1=1,

b2=1;

00

00

无

s1<<1|1-b1,

s2<<1|b2;

b1=0,

b2=0;

 

 

 

参考代码：

#include <iostream>#include <cstdio>#define LL long longusing namespace std;int n, m, x;LL f[12][1 << 12];//b1,b2,分别标记上一列队下一列的影响void dfs (int k, int last, int now, int b1, int b2) {	if (k == m){              if(!b1&&!b2)              f[x][now] += f[x - 1][last];              return;	}	if (!b1 && !b2) {		dfs (k + 1, last << 1 , now << 1 | 1, 0, 0);		dfs (k + 1, last << 1 , now << 1 | 1, 1, 0);		dfs (k + 1, last << 1 , now << 1 | 1, 0, 1);	}	if (!b1)		dfs (k + 1, last << 1 , now << 1 | b2, 1, 1);	if (!b2) {		dfs (k + 1, last << 1 | (1-b1), now << 1 | 1, 0, 1);		dfs (k + 1, last << 1 | (1-b1), now << 1 | 1, 1, 1);	}	dfs (k + 1, last << 1 | (1-b1), now << 1 | b2, 0, 0);}int main() {	scanf ("%d %d", &n, &m);	if (n < m) swap (n, m);       f[0][ (1 << m) - 1] = 1;	for ( x = 1; x <= n; x++)		dfs (0, 0, 0, 0, 0);	printf ("%lld", f[n][ (1 << m) - 1]);}

　　

 

 


联系
我们