本文主要是介绍poj 2411 编程之美 4.2 瓷砖覆盖地板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：用 1 * 2 的瓷砖覆盖 n * m 的地板，问共有多少种覆盖方式？
思路：用2进制的01表示不放还是放，第i行只和i-1行有关，枚举i-1行的每个状态，推出由此状态能达到的i行状态：如果i-1行的出发状态某处未放，必然要在i行放一个竖的方块，所以我对上一行状态按位取反之后的状态就是放置了竖方块的状态。
然后用dfs搜索在i行放横着的方块的所有可能，并且把这些状态累加上i-1的出发状态的方法数，如果该方法数为0，直接continue。
#include <stdio.h>
#include <string.h> /** n * m 的地板 */
int n,m; /** dp[i][j] = x 表示使第i 行状态为j 的方法总数为x */
__int64 dp[12][2049]; /* 该方法用于搜索某一行的横向放置瓷砖的状态数,并把这些状态累加上row-1 行的出发状态的方法数 * @name row 行数 * @name state 由上一行决定的这一行必须放置竖向瓷砖的地方，s的二进制表示中的1 就是这些地方 * @name pos 列数 * @name pre_num row-1 行的出发状态为~s 的方法数 */
void dfs( int row, int state, int pos, __int64 pre_num )
{ /** 到最后一列 */ if( pos == m ){ dp[row][state] += pre_num; return; } /** 该列不放 */ dfs( row, state, pos + 1, pre_num ); /** 该列和下一列放置一块横向的瓷砖 */ if( ( pos <= m-2 ) && !( state & ( 1 << pos ) ) && !( state & ( 1 << ( pos + 1 ) ) ) ) dfs( row, state | ( 1 << pos ) | ( 1 << ( pos + 1 ) ), pos + 2, pre_num );
}
int main()
{ while( scanf("%d%d",&n,&m) && ( n || m ) ){ /** 对较小的数进行状压，已提高效率 */ if( n < m ){ n=n^m; m=n^m; n=n^m; } memset( dp, 0, sizeof( dp ) ); /** 初始化第一行 */ dfs( 1, 0, 0, 1 ); for( int i = 2; i <= n; i ++ ) for( int j = 0; j < ( 1 << m ); j ++ ){ if( dp[i-1][j] ){ __int64 tmp = dp[i-1][j]; /* 如果i-1行的出发状态某处未放，必然要在i行放一个竖的方块， * 所以我对上一行状态按位取反之后的状态就是放置了竖方块的状态 */ dfs( i, ( ~j ) & ( ( 1 << m ) - 1 ), 0, tmp ) ; } else continue; } /** 注意并不是循环i 输出 dp[n][i]中的最大值 */ printf( "%I64d\n",dp[n][(1<<m)-1] ); } return 0;
} Python Version:
def dfs(row, state, pos, prenum, maxcol, dp):#row: the current row#state: the state of the current line#pos: the pos of the current row#prenum: the count of dp[row-1][~state]if (pos == maxcol):dp[row][state] += prenumreturn#3 situations:#1. If the col in the previous row is not filled, it won't be considered in the dfs codes since we don't store of the previous line in dfs codes#2. No matter whether the col is filled, move to the nextdfs(row, state, pos+1, prenum, maxcol, dp)#3. Fill two consecutive colsif ((pos+1 <= maxcol-1) and (state & (1 << pos) == 0) and (state & (1 << (pos+1)) == 0) ):dfs(row, state | (1 << pos) | (1 << (pos+1)), pos+2, prenum, maxcol, dp)def cal(m, n):if (m > n):m, n = n, mdp = [[0 for i in range(0, (1<<m)+1)] for j in range(0, n+1)]dfs(1, 0, 0, 1, m, dp)for i in range(2, n+1):for j in range(0, 1 << m):if (dp[i-1][j] != 0):#Consider situation 1 here:dfs(i, (~j) & ((1<<m)-1), 0, dp[i-1][j], m, dp)return dp[n][(1<<m)-1]if __name__ == '__main__':res = cal(7,8)print(res)扩展：
用p*q的瓷砖能覆盖M*N的地板的充要条件是：（这是一个判定问题，并不需要求方法数）
1。第一行和第一列可以被覆盖
2。m或n可以被p整除并且m或n可以被q整除
简单证明：
①当m(或n)被p 整除 & n(或m)被q 整除时，易知，一定能覆盖（一行行覆盖）
②当m(或n)被p * q 整除时，只要第一行的n 个格子能被覆盖，则一定能覆盖
③当①与②都不满足时，根据面积易知一定不能覆盖
也可以用反证法：
假设m*n被p*q的瓷砖铺满，那么一定
m= ap+bq
n=cp+dq
mn=acp^2+adpq+bcpg+bdq^2
mn=epq
假设a,b,c,d,e都不是0，而且a,b,c,d,p,q都是质数，那么acp=fq, bdq=gp, 但是这样的f,g是不存在的，所以a,c之一必定是0，b,d之一必定是0
更详细的参见下面的slides:
http://www-math.mit.edu/~rstan/transparencies/tilings.pdf这篇关于poj 2411 编程之美 4.2 瓷砖覆盖地板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
