题目描述

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

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

如下图所示：

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

每组测试用例占一行，包含两个整数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

算法1

(状压DP)

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N=12,M=1<<N;//左移N位相当于*2的N次方

int n,m;
long long f[N][M];//这种题不开long long绝对出问题
bool st[M];//记录有没有用过某个格子

int main()
{
    while(cin>>n>>m,n||m)//n行m列
    {
        memset(f,0,sizeof(f));//初始化

        for(int i=0;i<(1<<n);i++)//这样可以用一个一维的数组st[N]表示二维的状态,吃我降维打击.
        {
            st[i]=true;//好，这个位置占领了
            int cnt=0;
            for(int j=0;j<n;j++)
            {
                if(i>>j&1)//将i的二进制表示右移j位并与上1(只有位上都为1与后的结果才是1,例:101 & 111 =101,000 & 111=000)
                {
                    if(cnt&1) st[i]=false;//1的二进制表示为0000000...0000001
                    cnt=0;
                }
                else cnt++;
            }

            if(cnt&1) st[i]=false;
        }
        //DP过程
        f[0][0]=1;
        for(int i=1;i<=m;i++)//对每列进行尝试
        {
            for(int j=0;j<(1<<n);j++)
            {
                for(int k=0;k<(1<<n);k++)
                {
                    if((j&k)==0&&st[j|k])//不冲突且没用过
                    f[i][j]+=f[i-1][k];
                }
            }
        }

        printf("%lld\n",f[m][0]);
    }

    return 0;
}