铺砖问题（状压dp） --《挑战程序设计竞赛》p196页，个人的感想和做法

（ps：我发现很多博客都是将书上的代码，书上的解释打进去。就算了还打错代码，不晓得这样写博客有啥用）

题目：给定n*m的格子，每个格子被染成了黑色或者白色。现在要用1 * 2 的砖块覆盖这些格子，要求块与块之间互相不重叠，且覆盖了所有白色的格子，但不覆盖任意一个黑色格子。求一个有多少种覆盖方法，输出方案数对M取余后的结果。

（整张题目图片放上去会变得畸形。。。）

一些碎碎念：

看到这道题我首先想到的不是dp而是开关问题，根据二维开关问题我们可以遍历第一行所有状态，然后接下来所有情况都会被确定，然鹅这道题并不是。这道题多了一种方法，就是同一行之间就可以覆盖，没办法通过前面那行状态确定这一行状态。too young

假如使用dp的话就需要遍历所有状态，看着这个数据量我认为行不通，好了然后我就凉了

下面是结合书上解释我的看法：

这道题可以使用状态压缩dp去做，dp表示：从起点到当前格子覆盖格子的所有可能性（注：下文的可能性就指的是这个可能性），最大的可能是遍历 15*15*2^15≈10^4，完全可以接受。。

同样受到开关问题的启发，我们可以从第一行最左边开始，对于已经处理完毕的白色，一定都被覆盖成黑色。对于状态压缩我们就可以压缩当前点以及其往后的m-1个格子（一共m个格子就是一行，关于为什么面会讲），对于dp，我们关键就是要直到它的状态如何转移，正在处理的格子的可能性由已经处理完毕的格子推出来，根据这一点，假如处理到的格子是白色，那么：

1.假如格子的覆盖是需要横放产生，那么横放的格子一定是 “已经处理的格子”+“正在处理的格子”，而不是“正在处理的格子”+“还未处理的格子”。这样这个格子的可能性就已经被前面格子计算过，也就等于前面那个格子。

 

2.同理，假如当前格子的覆盖是需要竖着放置产生，那么一定是上面格子（已经处理过的格子）竖着放压到下面那个格子

 

这样一来，对于一个白色格子，那么他的可能性就等于横放的可能性（左边那个）+竖放可能性（上面那个）。

那么假如正在处理的格子是黑色的，也就是不需要被覆盖呢，那么下一个处理的格子的可能性就等于这一个格子的可能性。

 

上述就是如何状态转移

那么为什么要压缩m个格子的状态呢，我觉得是：在m个格子以前，一定都处理好了，不需要再考虑他们，在m个格子以后，他们还不能够对当前处理有影响，因此也不理他们。

忽然有点事，未完待续。。

贴代码先

#include<bits/stdc++.h>
using namespace std;
bool M[17][17];
int dp[2][1<<15]; 
int main(){
	int n,m,mod;
	while(cin>>n>>m &&n&&m){
		cin>>mod;
		memset(dp,0,sizeof(dp));
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){ //从0开始后面会好操作一点 
				char input; cin>>input;
				if(input=='.') M[i][j]=0; //0:白 1：黑，将0全变为1 
				else M[i][j]=1;
			}
		}
		int *now=dp[0],*nex=dp[1];
		now[0]=1;
		for(int i=n-1;i>=0;i--){ //从n-1 开始会方便二进制表示状态 
			for(int j=m-1;j>=0;j--){
				for(int used=0;used< (1<<m) ;used++){ //遍历状态,这里反过来表示  
					if(used>>j & 1 || M[i][j]){ //假如这个位置被用了或者是1 不用填 
						nex[used]=now[used & ~(1<<j)];  
					} 
					else{
						int res=0;
						if(j+1<m && !(used>>(j+1)&1) && !M[i][j+1]){ //横着放 
							res+=now[used|1<<(j+1)];
						}
						if(i+1<n && !M[i+1][j] ){ //竖着放 
							res+=now[used|1<<j];
						}
						nex[used]=res%mod;
					} 
					
				}
				swap(now,nex);
			}
		}
		cout<<now[0]<<endl;
	}
	return 0; 
}
/*
3 3 100
. . .
. X .
. . .
*/