解决此题的预备知识：1、动态规划 2、位运算
然后局限性：min(n,m)不能太大
首先我们可以注意到，一块砖只会影响上下两行的，我们设为n行m列（n>=m）的一个地面要铺满瓷砖，如果动态规划的话，我们可以这样想,用S表示某一行的状态，f[i,S]表示表示前i-1行都铺满的情况下，第i行状态为S有多少种铺出来的可能，那么，有动态规划可知，f[i,S]=SUM{f[i-1,S’]} (当由f[i-1,S’]状态可以到达f[i,S]状态时)。
边界条件:f[1,0]=1; 答案：f[n+1,0]
然后就是状态S的表示，对于某一行的格子，只有两种状态：被铺了或者没有，我们用0和1表示，那么m列就表示为一个m位的2进制数。则使用一个f[1..n,0..2^m-1]的数组存储，如果要节省空间可以使用滚动数组。
具体实现时可以有状态f[i,S]开始搜索，对状态S搜索所有可能的铺满方案（即让S->2^m-1），同时记录下一行的状态S1，然后累加。具体参见写的程序，我写了很多注释，这里不大好说。
程序代码：
感觉还是没讲大清楚.....
[ 本帖最后由 czz5242199 于 2011-11-16 10:11 编辑 ]
然后局限性：min(n,m)不能太大
首先我们可以注意到，一块砖只会影响上下两行的，我们设为n行m列（n>=m）的一个地面要铺满瓷砖，如果动态规划的话，我们可以这样想,用S表示某一行的状态，f[i,S]表示表示前i-1行都铺满的情况下，第i行状态为S有多少种铺出来的可能，那么，有动态规划可知，f[i,S]=SUM{f[i-1,S’]} (当由f[i-1,S’]状态可以到达f[i,S]状态时)。
边界条件:f[1,0]=1; 答案：f[n+1,0]
然后就是状态S的表示，对于某一行的格子，只有两种状态：被铺了或者没有，我们用0和1表示，那么m列就表示为一个m位的2进制数。则使用一个f[1..n,0..2^m-1]的数组存储，如果要节省空间可以使用滚动数组。
具体实现时可以有状态f[i,S]开始搜索，对状态S搜索所有可能的铺满方案（即让S->2^m-1），同时记录下一行的状态S1，然后累加。具体参见写的程序，我写了很多注释，这里不大好说。
程序代码：
#include <stdio.h>
#include <stdlib.h>
int f[12][1024]; //最多支持10行10列 1023=2^10-1
int n,m,i,j;
void dfs(int dep,int now,int next) //搜索第dep位，现在这行的状态，下一行的状态
{
if (dep==m)
{
f[i+1][next]+=f[i][j]; return;
} //已搜索m位，状态转移
if (now&(1<<dep))
{
dfs(dep+1,now,next); return;
} //第dep位为1，即已铺过东西，跳到下一位
dfs(dep+1,now|(1<<dep),next|(1<<dep)); //在第dep位竖直铺一块砖，影响下一行的状态
if (((now&1<<dep)==0) && ((now&1<<(dep+1))==0) && (dep+1<m))
dfs(dep+2,now|(1<<dep)|1<<(dep+1),next); //如果可以的话再第dep和dep+1位横着铺一块砖，不影响下一行的状态
}
int main()
{
scanf("%d%d",&n,&m);
memset(f,0,sizeof(f));
f[1][0]=1; //边界条件
for (i=1; i<=n; i++)
for (j=0; j<(1<<m); j++) //状态由0-2^m-1，位运算实现
if (f[i][j]) dfs(0,j,0);
printf("%d\n",f[n+1][0]);
system("pause");
}
感觉还是没讲大清楚.....
[ 本帖最后由 czz5242199 于 2011-11-16 10:11 编辑 ]
