-
Notifications
You must be signed in to change notification settings - Fork 0
/
Q66.java
89 lines (74 loc) · 1.94 KB
/
Q66.java
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
85
86
87
88
89
public class Q66 {
static final int HEIGHT = 3;
static final int WIDTH = 4;;
static int[][] degree = new int[HEIGHT + 1][WIDTH + 1];
static {
for (int i = 1; i < HEIGHT; i++) {
for (int j = 1; j < WIDTH; j++)
degree[i][j] = 4;
}
// 外枠(横)
for (int i = 1; i < WIDTH; i++) {
degree[0][i] = 3;
degree[HEIGHT][i] = 3;
}
// 外枠(縦)
for (int i = 1; i < HEIGHT; i++) {
degree[i][0] = 3;
degree[i][WIDTH] = 3;
}
// 四隅の分
degree[0][0] = degree[0][WIDTH] = degree[HEIGHT][0] = degree[HEIGHT][WIDTH] = 2;
}
public static void main (String[] args) {
long s = System.currentTimeMillis();
System.out.println(solve(0, 0, 0, false));
long e = System.currentTimeMillis();
System.out.println("time:" + (e-s) + "ms");
}
static int solve (int h, int w, int cnt_odd, boolean is_next_row) {
if (h == HEIGHT) {
cnt_odd += cnt_odd(h - 1) + cnt_odd(h);
return cnt_odd == 0 || cnt_odd == 2 ? 1 : 0;
}
if (is_next_row) {
cnt_odd += cnt_odd(h - 1);
if (cnt_odd > 2) return 0;
}
int ret = 0;
boolean flg = w + 1 == WIDTH;
int nh = flg ? h + 1 : h;
int nw = flg ? 0 : w + 1;
// パターン1
ret += solve(nh, nw, cnt_odd, flg);
// パターン2
degree[h][w]++;
degree[h + 1][w + 1]++;
ret += solve(nh, nw, cnt_odd, flg);
degree[h][w]--;
degree[h + 1][w + 1]--;
// パターン3
degree[h + 1][w]++;
degree[h][w + 1]++;
ret += solve(nh, nw, cnt_odd, flg);
degree[h + 1][w]--;
degree[h][w + 1]--;
// パターン4
degree[h][w]++;
degree[h + 1][w]++;
degree[h][w + 1]++;
degree[h + 1][w + 1]++;
ret += solve(nh, nw, cnt_odd, flg);
degree[h][w]--;
degree[h + 1][w]--;
degree[h][w + 1]--;
degree[h + 1][w + 1]--;
return ret;
}
static int cnt_odd (int row) {
int ret = 0;
for (int i = 0; i <= WIDTH; i++)
if (degree[row][i] % 2 == 1) ret++;
return ret;
}
}