题目描述

求把NM的棋盘分割成若干个12的的长方形，有多少种方案。

例如当N=2，M=4时，共有5种方案。当N=2，M=3时，共有3种方案。

如下图所示：

2411_1.jpg

输入格式
输入包含多组测试用例。

每组测试用例占一行，包含两个整数N和M。

当输入用例N=0，M=0时，表示输入终止，且该用例无需处理。

输出格式
每个测试用例输出一个结果，每个结果占一行。

数据范围
1≤N,M≤11

样例

输入样例：
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0
输出样例：
1
0
1
2
3
5
144
51205

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int N=12,M=1<<N; //N表示列数，因为要多枚举一行，所以+1，但N不能太大，否则M太大。M表示方案数
typedef long long LL;
LL f[N][M]; //防止超时
bool st[M]; //st表示状态是否合法

int main()
{
    int n,m;
    while(cin>>n>>m,n||m)  //为了防止代码超时，先预处理出所有合法的状态。n||m是题目已知的输入终止条件
    {
        for(int i=0;i<1<<n;i++) //枚举所有状态
        {
            int cnt=0; //cnt表示当前位上的1与上一个1之间0的个数
            st[i]=true; //初始化st数组
            for(int j=0;j<n;j++) //状态i由n位二进制数表示
            {
                if(i>>j&1)  //1.如果i的当前位是1，那么需要判断下它与上一个1之间0的个数，从而判断此状态是否合法
                {
                    if(cnt&1) st[i]=false;//cnt&1可以判断cnt是否为奇数。若是奇数，那么状态i不合法
                    cnt=0; //由于cnt是表示当前位上的1与上一个1之间0的个数，所以要在判断下一位之前清0
                }
                else cnt++;//2.如果i的当前位是0，那么需要cnt++
            }
            if(cnt&1) st[i]=false;//这里再次判断cnt的原因是，为了避免漏掉状态i的最后一位是0的情况
        }

    //预处理完所有合法状态之后可以开始处理数据
    memset(f,0,sizeof f);//初始化f
    f[0][0]=1;   //f[0][0]算是一种合法方案
    for(int i=1;i<=m;i++)  // 除f[0][0]=1之外，f[0][j]=0所以从i=1开始。i表示列
        for(int j=0;j<1<<n;j++) //枚举所有i-1列到i的状态
            for(int k=0;k<1<<n;k++)//枚举所有i-2列到i-1的状态
                if((j&k)==0 && st[j|k])//(j&k)记得加括号.k能否转移到j的条件:1）j和k不能在同一行同时为1；2）此时i-1的状态是合法的。
                //j|k得到的是i-1列此时的状态，如j=00100,k=00011,j|k=00111,判断st[00111]是否属于上面预处理出来合法的状态中的一个
                    f[i][j]+=f[i-1][k];//若合法，则求和即可

    cout<<f[m][0]<<endl;//由f[i][j]的集合定义得f[m][0]就是答案：前m-1列已经摆好，且从第m-1列没有伸到m列的方格。
    }
    return 0;
}