题目链接：

题目大意：在h*w的矩阵里铺满1*3的小矩阵，共有多少种方法

Sample Input

3 33 100 0

Sample Output

228

分析：状态压缩DP，跟ZOJ 1100 及其相识，不过那道题目使用1*2的木板平铺，题解链接：

　　但是不能照搬这道题目的方法，3^9约等于20000，两次循环的话会超时，所以每次只找符合条件的状态。

　　每个格子有三种状态0,1,2， 0----横放或者竖放的第三个格子 对下层没有影响，1----竖放的中间那个格子  对下一层有影响，2----竖放的第一个格子    对下两层有影响。

　　dp[i][j]表示到第i层状态为j的方法数。     

代码如下：

1 # include
     
       2 # include
      
        3 # include
       
         4 # define LL long long 5 LL dp[31][20000]; 6 int h,w;    //高度、宽度 7 int zt,row; //状态、行数 8 int pos[10],dig[10]; 9 void init()10 {11     pos[0] = 1;12     for(int i=1; i<=9; i++)13         pos[i] = pos[i-1]*3;14 }15 16 void get()  //得到该状态3进制下的各个位上的数字17 {18     int s=zt,len = 0;19     memset(dig,0,sizeof(dig));20     while(s)21     {22         dig[len++] = s%3;23         s = s/3;24     }25 }26 27 void dfs(int col,int s)     //这一行状态s受zt的影响，col表示列，作为标记28 {29     if(col==w)  //当到达最大宽度时，需要运算30     {31         dp[row][s] += dp[row-1][zt];32         return;33     }34     if(dig[col]==0) //上一层是035     {36         if(col+2