蒙德里安的梦想

通过找到合理的，合法的横放1*2矩形的状态，来确定结果。
（初次写题解，如有不正确的地方，请大佬指正。）

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;
const int N=12,M=1<<12;
LL f[N][M];
bool str[M];
vector<int> A[M];
int n,m;

int main()
{
    while(cin>>n>>m,n||m)
    {
        for(int i=0;i<1<<n;i++)
        {
            int cnt=0;
            bool is_valid=true;
            for(int j=0;j<n;j++)
            {
                if(i>>j&1)//判断第j层是否要放
                {
                    if(cnt&1)//如果放的话，判断在放置点的上方有奇数还是偶数个空的方格。
                    {
                        is_valid=false;//如果是奇数个，则i所表示的方法不合理。
                        break;
                    }
                    cnt=0;//如果是偶数个，则当前判断到i的第j位，i所表示的方法还是合理的，is_valid是true。
                    //cnt不清零也是可以的，因为不清零cnt是偶数，表示了之前的空格状态，不影响后续继续操作时
                    //cnt的奇偶。
                }
                else cnt++;//因为不放矩形，所以此方格为空，cnt加一。
            }

            if(cnt&1)is_valid=false;//可能存在一些情况使得在关于j的for循环中没有判断最后一层
            //放还是不放，比如11000（这种状态是不合理的，因为在最后一层还可以放矩形使
            //其成为11001，这样能够更大的划分，同时还有连续的偶数个空格放置竖的矩形，
            //所以在外加一层判断那以后，得出最后结论），所以额外加一层判断。
            str[i]=is_valid;//i的这种放置状态是合理还是不合理。
        }

        for(int i=0;i<1<<n;i++)
        {
            A[i].clear();//有多组测试数据，把上一组的数据清空后再用。
            for(int j=0;j<1<<n;j++)
            {
                if((i&j)==0&&str[i|j])
//在这里假设此时计算的是第k列：则i是k-1列，j是k+1列，有此前的推理可知
//假如i与j同时都要横向放置的话，则第k列会有重复的矩形放置，所以说要确保（i&j）==0。
//上述合理以后，则i与j所放置的矩形的并集即为k的状态，此时要判断k的放置方法是否合理，
//即是否满足上述预处理中的合理状态。
                {
                    A[i].push_back(j);
                }
            }
        }

        memset(f,0,sizeof f);//有多组测试数据，把上一组的数据清空后再用。
        f[0][0]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=0;j<1<<n;j++)
            {
                for(int k=0;k<A[j].size();k++)
                {
                    f[i][j]+=f[i-1][A[j][k]];
                }
            }
        }

        cout<<f[m][0]<<endl;
    }

    return 0;
}