2013-08-11 21:42:59Morris
[UVA][插頭DP] 11270 - Tiling Dominoes
A. Tiling Dominoes
| A. Tiling Dominoes |
Problem
Given a rectangular grid, with dimensions m x n, compute the number of ways of completely tiling it with dominoes. Note that if the rotation of one tiling matches another, they still count as different ones. A domino is a shape formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a matching in the grid graph formed by placing a vertex at the center of each square of the region and connecting two vertices when they correspond to adjacent squares. An example of a tiling is shown below.
The Input
The input will consist of a set of lines with m n, given the restriction n*m<101.
The Output
For each line of input, output the number of tilings in a separate line.
Sample Input
2 10 4 10 8 8
Sample Output
89 18061 12988816
Problem setter: Josh Bao
Alternative Solution: Rodrigo Burgos
圖片來源http://www.cnblogs.com/crazyac/articles/1966135.html
2011022709494197.jpg
[UVA][插頭DP] 11270 - Tiling Dominoes
雖然說是插頭 DP，但是這題算是簡化了，有人撐作為輪廓線dp。
考慮插入的 1x2 躺著的那個話，左方必須為空，上方為非空。
考慮插入的 2x1 立著的那個話，上方為空。
不打算放的話，即留給下面那格放 2x1, 那麼上方要非空, 不然會有非填滿的情況。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
int n, m;
while(scanf("%d %d", &n, &m) == 2) {
if(n < m) swap(n, m);
long long dp[2][1024] = {};// max(n, m) = 10
int flag = 0;
dp[0][(1<<m)-1] = 1;
int left, up;
int i, j, k;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
memset(dp[!flag], 0, sizeof(dp[!flag]));
for(k = (1<<m)-1; k >= 0; k--) {
if(j == 0) left = 1;
else left = (k>>(j-1))&1;
up = (k>>j)&1;
if(up == 0)//set 1 x 2
dp[!flag][k|(1<<j)] += dp[flag][k];
if(left == 0 && up != 0)//set 2 x 1
dp[!flag][k|(1<<j)|(1<<(j-1))] += dp[flag][k];
if(up)//set null
dp[!flag][k^(1<<j)] += dp[flag][k];
}
flag = 1-flag;
}
}
printf("%lld\n", dp[flag][(1<<m)-1]);
}
return 0;
}