POJ 2411Mondriaan's Dream(类似hdu1992铺砖问题)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

long long dp[15][15][2050];

void dfs(int r,int c,int cur,int nex,int m)
{
    if(c>=m)
    {
        dp[r+1][m][nex]+=dp[r][m][cur];
        return;
    }
    if(!(cur&(1<<c)))
    {
        dfs(r,c+1,cur,nex|(1<<c),m);   //可以放一个1
        if(c<=m-2&&(!(cur&(1<<(c+1)))))  //可以放00
            dfs(r,c+2,cur,nex,m);
    }
    else
        dfs(r,c+1,cur,nex,m);
}

int main()
{
    int i,j,k;
    memset(dp,0,sizeof(dp));
    for(i=0;i<15;i++)
        dp[0][i][0]=1;   //把框框的列数确定找每一行的

    for(i=1;i<12;i++)  //确定列数
    {
        int tmp=1<<i;
        for(j=0;j<12;j++)   //确定每一行
        {
            for(k=0;k<tmp;k++)
                if(dp[j][i][k])
                    dfs(j,0,k,0,i);
        }
    }

    int n,m;
    while(cin>>n>>m)
    {
        if(n+m==0) break;
        cout<<dp[n][m][0]<<endl;
    }
    return 0;
}