Enumerate the Ways to Cover a M*N Matrix with Dominoes

Problem: Given a M*N matrix, enumerate all the different ways to cover it with dominoes (1*2 blocks). For example, for a 1*2 matrix, there are only one way; for a 2*2 matrix, there is 2 ways. The original problem is from poj 2411.

Solution: We can definitely use backtracking, but more efficient approaches should be DP. First we need to think what are the states and how to represent them. Obviously, the arrangement of dominoes on the matrix is the state. There might be multiple ways to represent them. Here we just introduce one approach: every cell in the matrix is either 0 or 1; "0" means the domino block is placed horizontally and "1" means the domino is placed vertically. If a cell, say a[i,j] is marked as "1", a[i+1,j] can't be marked as "1". Then we can use the binary sequence to represent the status of one row. For example, "0000" means two dominoes lay horizontally. Besides, there are several key observations:

• For each row, there must be even number of consecutive "zero"s. Otherwise, we cannot fully cover a row.
• The status of current row only depends on the previous row. It means we only need to look back one row.
• Then we build a status matrix d[i][s] with i as the row number and s as a particular state. d[i][s] means the number of ways to arrange a matrix with current state (all i-1 rows are filled and the ith row is with state s). Therefore,  d[i][s] =sum_{all possible d[i-1][k]}. 
• How to decide  d[i-1][k], first, s&k should be zero, which is to conform to the constraint " a[i,j] is marked as "1", a[i+1,j] can't be marked as "1". Second, s|k should be a valid arrangement, which is to conform to the constraint " there must be even number of consecutive zeros". Then the cell d[M][0] stores the answer to our problem.

typedef long long LL;
const int maxn = (1 << 12);

LL h , w , dp[12][maxn];

//to decide if it contains odd number of consecutive "zero"s
bool judge(LL s)
{
     LL cnt = 0;
     for(LL i=0; i < w; i++)
     {
         LL t = s & 1;
         if(t)
         {
             if(cnt & 1)
                 return false;
             else
                 cnt = 0;
         } else
             cnt ++;
         s >>= 1;
     }
     if(cnt & 1)
         return false;
     return true;
}

int main()
{
     while(~scanf("%lld %lld", &h, &w))
     {
         if(h == 0 && w == 0)
             break;
         memset(dp , 0 , sizeof(dp));

         //initialize the state in row 1
         for(LL i=0; i < (1 << w); i++)
         {
             if(judge(i))
             {
                 dp[1][i] = 1;
             }
         }
         for(LL i=2; i <= h; i++)
         {
              for(LL j=0; j < (1 << w); j++)
              {
                 for(LL k=0; k < (1 << w); k++)
                 {
                     LL t = j & k;
                     if(t)
                          continue;
                      //so here "t" is the actual state 
                      //on the current row, since if 
                      //the position in the above 
                      //row is marked as "1", the 
                      //position in current row must 
                      //be "0", otherwise this 
                      //iteration will be skipped by 
                      //previous "continue". But, 
                      //even though it is "0", we 
                      //need to count it as "1", 
                      //since it cannot hold domino.
                      //This is what "t=j|k;" 
                      //really means.

                      t = j | k;
                     if(judge(t))
                      {
                         dp[i][j] += dp[i - 1][k];
                      }
                 }
              }
          }
         printf("%lld\n", dp[h][0]);
     }

}

The code is from xIao.wU.