意甲冠军：

要在m行n陆行，有一些格您可以种树，别人做不到的。不相邻的树，我问了一些不同的共同拥有的法律。

分析：

从后往前种，子问题向父问题扩展，当种到某一格时仅仅有他和他后面的n-1个格子的情况对它有影响。故对这n个格子进行编码为状态S,表示种完（多米诺骨牌那题是放置前。注意差别，都可行）这n个格子的状态。父问题由稍小子问题逐步解决，正是动态规划的思想。

代码：

//poj 3254

//sep9

#include <iostream>

using namespace std;

const int maxN=14;

const int mod=100000000;

int land[maxN][maxN];

int dp[2][1<<maxN];

int m,n;

int main()

{

	scanf("%d%d",&m,&n);

	int i,j,used;

	for(i=0;i<m;++i)

		for(j=0;j<n;++j)

			scanf("%d",&land[i][j]);

	int *cur=dp[0],*nxt=dp[1];

	cur[0]=1;

	for(i=m-1;i>=0;--i)

		for(j=n-1;j>=0;--j){

			for(used=0;used<1<<n;++used){

				if(land[i][j]==0){

					if(used>>j&1)

						nxt[used]=0;

					else{

						nxt[used]=cur[used];

						nxt[used]+=cur[used|(1<<j)];

						nxt[used]%=mod;

					}

				}

				else{

					int res=0;

					if((used>>j&1)&&(used>>(j+1)&1)){

						res=0;

					}else if(!(used>>j&1)&&(used>>(j+1)&1)){

						res=cur[used];

						res+=cur[used|(1<<j)];

					}else if((used>>j&1)&&!(used>>(j+1)&1)){

						res=cur[used&(~(1<<j))];

					}else if(!(used>>j&1)&&!(used>>(j+1)&1)){

						res=cur[used];

						res+=cur[used|(1<<j)];

					}

					nxt[used]=res%mod;

				}

			}

			swap(cur,nxt);

		}

	int sum=0;

	for(int i=0;i<1<<n;++i){

		sum+=cur[i];

		sum%=mod;

	}

	printf("%d",sum);

	return 0;

}