forked from y-tetsu/math_puzzle
-
Notifications
You must be signed in to change notification settings - Fork 0
/
q67.py
66 lines (53 loc) · 1.74 KB
/
q67.py
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
#!/usr/bin/env python
"""
Q67
"""
import itertools
W, H = 6, 5
def is_adjacent(ptn):
for col in range(H):
for row in range(W):
if ptn[col * W + row] == "1":
if col - 1 >= 0 and ptn[(col - 1) * W + row] == "1":
return True
if col + 1 < H and ptn[(col + 1) * W + row] == "1":
return True
if row - 1 >= 0 and ptn[col * W + (row - 1)] == "1":
return True
if row + 1 < W and ptn[col * W + (row + 1)] == "1":
return True
def is_separated(ptn):
start = 0
for index, value in enumerate(ptn):
if value == "0":
start = index
break
else:
return True
cnt1 = ptn.count("0")
cnt2 = check(ptn, start, [i for i in ptn])
if cnt1 == cnt2:
return False
return True
def check(ptn, start, checked):
checked[start] = "2"
col = start // W
row = start % W
cnt1, cnt2, cnt3, cnt4 = 0, 0, 0, 0
if col - 1 >= 0 and checked[(col - 1) * W + row] == "0":
cnt1 = check(ptn, (col - 1) * W + row, checked)
if col + 1 < H and checked[(col + 1) * W + row] == "0":
cnt2 = check(ptn, (col + 1) * W + row, checked)
if row - 1 >= 0 and checked[col * W + (row - 1)] == "0":
cnt3 = check(ptn, col * W + (row - 1), checked)
if row + 1 < W and checked[col * W + (row + 1)] == "0":
cnt4 = check(ptn, col * W + (row + 1), checked)
return checked.count("2")
if __name__ == '__main__':
CNT = 0
for ptn in itertools.product("01", repeat=W*H):
if not is_adjacent(ptn):
if not is_separated(ptn):
CNT += 1
print(CNT)
print("result =", CNT)