题目大意:用 2*1 或者2*2-1的格子覆盖M*N的矩阵,有多少种覆盖方式。

分析:容易知道有以下6种放置方式。

Hardwood floor - SGU 131(状态压缩)-LMLPHP

然后用深搜的方法直接搞出来就行了,不过要使用两个变量来判断本位是否受影响。如果本行的放置可以影响上一行,比如(1,3,4,5,6)那么所影响的位置为0,如果没有受到影响那么就是1。

代码如下:

=====================================================================================================================

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std; const int MAXN = ;
const int Bit = ; long long dp[MAXN][<<Bit];
int M, N; void DFS(int row, int col, int now, int pre, bool uNow, bool uPre)
{///row表示所在行,col表示列,now表示本行的状态,pre表示上一行的状态
///uNow uPre表示本列和上一列是否收到影响,1表示受影响,0表示没有
if(col == N)
{
if(!uNow && !uPre)
dp[row][now] += dp[row-][pre];
return ;
} if(!uNow)
{
if(!uPre)
{
DFS(row, col+, now<<|, pre<<, , );
DFS(row, col+, now<<|, pre<<, , );
DFS(row, col+, now<<|, pre<<, , );
}
DFS(row, col+, now<<|, pre<<|(!uPre), , );
DFS(row, col+, now<<|, pre<<|(!uPre), , );
}
if(!uPre)
DFS(row, col+, now<<|uNow, pre<<, , );
DFS(row, col+, now<<|uNow, pre<<|(!uPre), , );
} int main()
{
scanf("%d%d", &M, &N); dp[][(<<N)-] = ;
for(int i=; i<=M; i++)
DFS(i, , , , , ); printf("%lld\n", dp[M][(<<N)-]); return ;
}
05-11 19:54