Algorithm-and-Data-Structure/AlgorithmCode/TilingDominoes.java at master · lemidia/Algorithm-and-Data-Structure · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/**
 * Solution to Tri Tiling (https://open.kattis.com/problems/tritiling)
 *
 * <p>Explanation video: https://www.youtube.com/watch?v=yn2jnmlepY8
 *
 * <p>Solution by: William Fiset
 */
importjava.util.*;

publicclassTilingDominoes {
staticScannersc = newScanner(System.in);

publicstaticvoidmain(String[] args) {
while (true) {
intn = sc.nextInt();
if (n == -1) break;
// Solution1:
System.out.println(solution1(n));

// Alternative solution:
// System.out.println(solution2(n));
 }
 }

// Tile states 0...7 representations:
//
// 0: 0 1: 1 2: 0 3: 1
// 0 0 1 1
// 0 0 0 0
//
// 4: 0 5: 1 6: 0 7: 1
// 0 0 1 1
// 1 1 1 1
privatestaticintsolution1(intn) {
int[][] dp = newint[n + 1][1 << 3];
dp[0][7] = 1;
for (inti = 1; i < n + 1; i++) {
// The number of empty states for this column is the number
// of full states in the previous column.
dp[i][0] += dp[i - 1][7];

dp[i][1] += dp[i - 1][6];

// State 2 doesn't contribute to the number of tilings
// dp[i][2] += dp[i-1][5];

dp[i][3] += dp[i - 1][7];
dp[i][3] += dp[i - 1][4];

dp[i][4] += dp[i - 1][3];

// State 5 doesn't contribute to the number of tilings
// dp[i][5] += dp[i-1][2];

dp[i][6] += dp[i - 1][7];
dp[i][6] += dp[i - 1][1];

dp[i][7] += dp[i - 1][3];
dp[i][7] += dp[i - 1][6];
dp[i][7] += dp[i - 1][0];
 }
// printMatrix(dp);
returndp[n][7];
 }

privatestaticvoidprintMatrix(int[][] dp) {
for (inti = 0; i < dp.length; i++) {
for (intj = 0; j < 1 << 3; j++) {
System.out.printf("% 5d,", dp[i][j]);
 }
System.out.println();
 }
 }

privatestaticintsolution2(intn) {
int[] dp = newint[n + 4];
dp[0] = 1;
dp[2] = 3;
for (inti = 4; i < n + 4; i += 2) {
dp[i] = 4 * dp[i - 2] - dp[i - 4];
 }
returndp[n];
 }
}