Sgu/131

状态压缩DP，转移的时候情况很多，要一个个写出来理清楚再写。 一行一行推，opt1为上一行的状态，opt2为当前行的状态， u1,u2分别为上下两行是否与左边相连而凸出来。

/*
     Case   1    2    3    4          5          6          7
            |    +-   |    L  or U    L| or U|   -+ or -+   L or U or L or U
            |    |    +-   --    --   -+    -+   W|    L|   W    W    L    L
 
     old    L     : connect with Left block
            U     : connect with Upper block
     new    - | + : describe the shape of forms
     empty  W     : NO put this block, wait for the forms of next row
*/
#include <stdio.h>
using namespace std;
#define LL long long
 
int n, m, i;
LL f[10][512];
 
void dfs(int j, int opt1, int opt2, int u1, int u2)
{
     if (j == m)
     {
        if (!u1 && !u2) f[i + 1][opt2] += f[i][opt1]; 
        return;
     }
     // Put this block
     if (!u2)
     {
        if (!u1)
        {
           dfs(j+1, opt1<<1, (opt2<<1)+1, 0, 0); // Case 1
           dfs(j+1, opt1<<1, (opt2<<1)+1, 1, 0); // Case 2
           dfs(j+1, opt1<<1, (opt2<<1)+1, 0, 1); // Case 3
        }
        dfs(j+1, (opt1<<1)+1-u1, (opt2<<1)+1, 0, 1); // Case 4
        dfs(j+1, (opt1<<1)+1-u1, (opt2<<1)+1, 1, 1); // Case 5
     }
     // NO put or Already put this block
     if (!u1) dfs(j+1, opt1<<1, (opt2<<1)+u2, 1, 1); // Case 6
     dfs(j+1, (opt1<<1)+1-u1, (opt2<<1)+u2, 0, 0); // Case 7
}
 
int main()
{
    scanf("%d %d", &n, &m);
    if (n < m) { n ^= m; m ^= n; n ^= m; }
    f[0][(1<<m)-1] = 1;
    for (i = 0; i < n; ++i)
        dfs(0, 0, 0, 0, 0);
    printf("%I64d", f[n][(1<<m)-1]);
    return 0;
}
// From FingerSed

6种放置方法分别枚举

/*
##     #.     ##    ##     #.   .#
..     #.     #.    .#     ##   ##
1      2      3      4      5    6
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long int LL;
const int maxn = 1<<11;
#define bin(i) (1<<i)
#define emp(a,i) (!(a&bin(i)))
int n,m,full;
LL g[maxn],f[maxn]; //f为当前行状态 g为枚举当前行状态后,对下一行的影响 
void dfs(int a,int b,LL k){
	if(a == full){ //要求铺满
		g[b] += k;
		return ;
	}
	for(int i=0;i<m;++i)if(emp(a,i)){
		if(i+1<m&&emp(a,i+1)){
			dfs(a|bin(i)|bin(i+1),b,k); //#1
			if(emp(b,i)) dfs(a|bin(i)|bin(i+1),b|bin(i),k);//#3
			if(i+1<m&&emp(b,i+1))dfs(a|bin(i)|bin(i+1),b|bin(i+1),k); //#4
		}
		if(emp(b,i)){
			dfs(a|bin(i),b|bin(i),k); //#2
			if(i+1<m&&emp(b,i+1))dfs(a|bin(i),b|bin(i)|bin(i+1),k); //#5
			if(i>=1&&emp(b,i-1))dfs(a|bin(i),b|bin(i)|bin(i-1),k); //#6
		}
		break; //每次进行一个状态的填充 
	}
}
int main()
{
	cin >> n >> m;
	full = (1<<m)-1; f[full] = 1;
	for(int k=0;k<=n;++k){//在首尾都加一行来避开统计,统一计数 
		for(int i=0;i<=full;++i)//枚举上一行状态
			if(f[i]) dfs(i,0,f[i]); //dfs枚举6个情况进行转移
		memcpy(f,g,sizeof(g));
		memset(g,0,sizeof(g));
	}
	cout <<f[0] <<endl;
	return 0;
}