SGU 131.Hardwood floor

时间:2021-03-11 00:38:24

时间限制: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 long
using 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]);
}