-
Notifications
You must be signed in to change notification settings - Fork 22
/
beaming_with_joy.py
156 lines (142 loc) · 5.38 KB
/
beaming_with_joy.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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
# Copyright (c) 2020 kamyu. All rights reserved.
#
# Google Code Jam 2017 Round 2 - Problem C. Beaming with Joy
# https://codingcompetitions.withgoogle.com/codejam/round/0000000000201900/0000000000201876
#
# Time: O(R * C)
# Space: O(R * C)
#
from sys import setrecursionlimit
from collections import defaultdict
# Template:
# https://github.com/kamyu104/GoogleCodeJam-2018/blob/master/World%20Finals/swordmaster.py
def strongly_connected_components(graph): # Tarjan's Algorithm, Time: O(|V| + |E|), Space: O(|V|)
def strongconnect(v, index_counter, index, lowlinks, stack, stack_set, result):
index[v] = index_counter[0]
lowlinks[v] = index_counter[0]
index_counter[0] += 1
stack_set.add(v)
stack.append(v)
for w in (graph[v] if v in graph else []):
if w not in index:
strongconnect(w, index_counter, index, lowlinks, stack, stack_set, result)
lowlinks[v] = min(lowlinks[v], lowlinks[w])
elif w in stack_set:
lowlinks[v] = min(lowlinks[v], index[w])
if lowlinks[v] == index[v]:
connected_component = []
w = None
while w != v:
w = stack.pop()
stack_set.remove(w)
connected_component.append(w)
result.append(tuple(connected_component))
index_counter, index, lowlinks = [0], {}, {}
stack, stack_set = [], set()
result = []
for v in graph:
if v not in index:
strongconnect(v, index_counter, index, lowlinks, stack, stack_set, result)
return result
class TwoSat(object):
def solve(self, __clauses):
graph = defaultdict(list)
for p, q in __clauses:
graph[-p].append(q)
graph[-q].append(p)
sccs, assignments = strongly_connected_components(graph), set()
for scc in sccs:
scc_set = set(scc)
if any(-v in scc_set for v in scc_set):
break
else:
for scc in sccs:
for v in scc:
if v not in assignments and -v not in assignments:
assignments.add(v)
return assignments
class CNFEncoder(object):
def __init__(self, cnf):
self.__cnf = cnf
self.__forward_map = {}
self.__reverse_map = {}
self.__clauses = []
def add(self, o1, v1, o2, v2):
self.__clauses.append((self.__encode(o1) * self.__sign(v1), self.__encode(o2) * self.__sign(v2)))
def solve(self):
return map(self.__decode, self.__cnf.solve(self.__clauses))
def __encode(self, obj):
if obj not in self.__forward_map:
key = len(self.__forward_map)+1
self.__forward_map[obj] = key
self.__reverse_map[key] = obj
return self.__forward_map[obj]
def __decode(self, key):
return self.__reverse_map[abs(key)], key > 0
def __sign(self, val):
return {True: 1, False: -1}[val]
def shoot(G, i, j, d):
def dfs(G, i, j, di, dj, curr):
ni, nj = i+di, j+dj
if not (0 <= ni < len(G) and 0 <= nj < len(G[0])) or G[ni][nj] == '#':
return curr
elif G[ni][nj] == '.':
curr.append((ni, nj))
return dfs(G, ni, nj, di, dj, curr)
elif G[ni][nj] == '/':
return dfs(G, ni, nj, -dj, -di, curr)
elif G[ni][nj] == '\\':
return dfs(G, ni, nj, dj, di, curr)
else:
return None
if d == '-':
path_left, path_right = dfs(G, i, j, 0, -1, []), dfs(G, i, j, 0, 1, [])
return None if path_right is None or path_left is None else path_right+path_left
elif d == '|':
path_up, path_down = dfs(G, i, j, -1, 0, []), dfs(G, i, j, 1, 0, [])
return None if path_up is None or path_down is None else path_up+path_down
def beaming_with_joy():
R, C = map(int, raw_input().strip().split())
G = [list(raw_input().strip()) for _ in xrange(R)]
shooters, empties = set(), {}
for i, r in enumerate(G):
for j, c in enumerate(r):
if c in "-|":
shooters.add((i, j))
elif c == '.':
empties[(i, j)] = []
cnf = CNFEncoder(TwoSat())
for s in shooters:
choice_mask = 0
for i, d in enumerate("-|", 1):
path = shoot(G, s[0], s[1], d)
if path is None:
continue
choice_mask |= i
for cell in path:
empties[cell].append((s, d))
if not choice_mask:
return "IMPOSSIBLE"
elif choice_mask == 1:
cnf.add(s, False, s, False)
elif choice_mask == 2:
cnf.add(s, True, s, True)
for choices in empties.itervalues():
if not choices:
return "IMPOSSIBLE"
elif len(choices) == 1:
cnf.add(choices[0][0], choices[0][1] == '|', choices[0][0], choices[0][1] == '|')
continue
elif len(choices) == 2:
cnf.add(choices[0][0], choices[0][1] == '|', choices[1][0], choices[1][1] == '|')
result = cnf.solve()
if not result:
return "IMPOSSIBLE"
for (i, j), is_vertical in result:
G[i][j] = "-|"[is_vertical]
return "POSSIBLE\n{}".format("\n".join(map(lambda x: "".join(x), G)))
MAX_R, MAX_C = 50, 50
BASE = 3
setrecursionlimit(BASE + (1+2*MAX_R*MAX_C))
for case in xrange(input()):
print 'Case #%d: %s' % (case+1, beaming_with_joy())