POJ2411 Mondriaan's Dream

Description

Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his 'toilet series' (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways.

Expert as he was in this material, he saw at a glance that he'll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won't turn into a nightmare!

Input

The input contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.

Output

For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.

题意：经典的用1*2或2*1骨牌堆满n*m矩阵，求方案数。

思路：首先可以知道要状压，要想办法把状态编码一下。

能不能把横着的设为11，竖着的设为00？

貌似可以，但是转移时就有问题了，当前位置上方是0的话，上面那个是已经和它上边摆好了还是需要和它下面，也就是当前位置一块儿放？

这样的编码是有问题的，解决不了上述问题。

应该这样：设横着的是11，竖着的是01，这是什么样的逻辑呢？

1表示这个位置已经摆好，与下一行无关，0表示这个位置与下一行有关。

这样的编码方式就解决了问题。

初始化：第一行必须满足--连续的1的数目必须是偶数。

后续不能像之前做的“一行不冲突”那样，也就是第一行做的那样。而应该遍历所有的状态，因为该行为奇数个连续1可能可以与上一行相适应。

·判断当前行与上一行是否冲突：就是上一行为0的位置这行必须为1，并且除去与上一行匹配的后这一行连续1的数目必须是偶数。

就是代码中的((bits&(~k))&s) == (bits&(~k))，把上一行的状态反转（因为1比0好处理），这里bits是((1<<m)-1)，不加bits的话int的10+，20+位原来是0现在就是1了。

以及check(s-(bits&(~k)))，check是检测是否连续的1的数目是偶数。

最好先预处理出所有的答案，这样比较快。

#include<iostream>
#include<cstring>
using namespace std;
#define ll long long
#define bits ((1<<m)-1)

ll n,m,f[12][1<<12],ans[12][12];

bool check(int s)
{
	bool ok=1;
	int cnt=0;
	for(int i=0;i<m;i++)
		if((1<<i)&s)cnt++;
		else
		{
			if(cnt&1){ok=0;break;}
			cnt=0;
		}
	if(cnt&1)ok=0;
	return ok;
}

void dp()
{
	memset(f,0,sizeof(f));
	for(int s=0;s<(1<<m);s++)if(check(s))f[0][s]=1;
	for(int i=1;i<n;i++)
	{
		for(int s=0;s<(1<<m);s++)
		{
			for(int k=0;k<(1<<m);k++)if(((bits&(~k))&s) == (bits&(~k))&&check(s-(bits&(~k))))
			{
				f[i][s]+=f[i-1][k];
			}
		}
	}
	for(int i=0;i<n;i++)ans[i+1][m]=f[i][(1<<m)-1];
}

int main()
{
	//freopen("input.in","r",stdin);
	for(m=1;m<=11;m++)
	{
		n=11;
		dp();
	}
	while(cin>>n>>m&&n)
	{
		cout<<ans[n][m]<<endl;
	}	
	return 0;
}