You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
100 lines
2.2 KiB
Java
100 lines
2.2 KiB
Java
public class DominoFill {
|
|
|
|
/**
|
|
* .....
|
|
* ..234
|
|
* 01
|
|
*/
|
|
public static int method1(int R, int C) {
|
|
int[] prev = new int[1 << C];
|
|
prev[(1 << C) - 1] = 1;
|
|
|
|
for (int r = 0; r < R; r++) {
|
|
for (int c = 0; c < C; c++) {
|
|
int[] cur = new int[1 << C];
|
|
for (int mask = 0; mask < 1 << C; mask++) {
|
|
if ((mask & (1 << c)) != 0) {
|
|
cur[mask ^ (1 << c)] += prev[mask]; // do nothing
|
|
|
|
if (c > 0 && (mask & (1 << (c - 1))) == 0) {
|
|
cur[mask | (1 << (c - 1))] += prev[mask]; // horizontal
|
|
}
|
|
} else {
|
|
cur[mask | (1 << c)] += prev[mask]; // vertical
|
|
}
|
|
}
|
|
prev = cur;
|
|
}
|
|
}
|
|
|
|
return prev[(1 << C) - 1];
|
|
}
|
|
|
|
/**
|
|
* .....
|
|
* ..012
|
|
* 34
|
|
*/
|
|
public static int method2(int R, int C) {
|
|
int[] prev = new int[1 << C];
|
|
prev[(1 << C) - 1] = 1;
|
|
|
|
for (int r = 0; r < R; r++) {
|
|
for (int c = 0; c < C; c++) {
|
|
int[] cur = new int[1 << C];
|
|
for (int mask = 0; mask < 1 << C; mask++) {
|
|
int nmask = (mask << 1) & ((1 << C) - 1);
|
|
if ((mask & (1 << (C - 1))) != 0) {
|
|
cur[nmask] += prev[mask]; // do nothing
|
|
|
|
if (c > 0 && ((mask & 1) == 0)) {
|
|
cur[nmask | 3] += prev[mask]; // horizontal
|
|
}
|
|
} else {
|
|
cur[nmask | 1] += prev[mask]; // vertical
|
|
}
|
|
}
|
|
prev = cur;
|
|
}
|
|
}
|
|
|
|
return prev[(1 << C) - 1];
|
|
}
|
|
|
|
// random test
|
|
public static void main(String[] args) {
|
|
for (int r = 1; r < 10; r++) {
|
|
for (int c = 1; c < 10; c++) {
|
|
int res1 = method1(r, c);
|
|
int res2 = method2(r, c);
|
|
if (res1 != res2)
|
|
throw new RuntimeException();
|
|
}
|
|
}
|
|
}
|
|
|
|
public static int method0(int R, int C) {
|
|
int[][][] dp = new int[R + 1][C][1 << C];
|
|
dp[0][C - 1][(1 << C) - 1] = 1;
|
|
|
|
for (int r = 1; r <= R; r++) {
|
|
for (int c = 0; c < C; c++) {
|
|
int[] prev = c > 0 ? dp[r][c - 1] : dp[r - 1][C - 1];
|
|
for (int mask = 0; mask < 1 << C; mask++) {
|
|
if ((mask & (1 << c)) != 0) {
|
|
dp[r][c][mask ^ (1 << c)] += prev[mask]; // do nothing
|
|
|
|
if (c > 0 && (mask & (1 << (c - 1))) == 0) {
|
|
dp[r][c][mask | (1 << (c - 1))] += prev[mask]; // horizontal
|
|
}
|
|
} else {
|
|
dp[r][c][mask | (1 << c)] += prev[mask]; // vertical
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return dp[R][C - 1][(1 << C) - 1];
|
|
}
|
|
}
|