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
|
import sys
import re
from copy import deepcopy
from math import gcd
from collections import defaultdict, Counter, deque
D = open(sys.argv[1]).read().strip()
L = D.split("\n")
G = [[c for c in row] for row in L]
R = len(G)
C = len(G[0])
for r in range(R):
for c in range(C):
if G[r][c] == "S":
sr, sc = r, c
up_valid = G[r - 1][c] in ["|", "7", "F"]
right_valid = G[r][c + 1] in ["-", "7", "J"]
down_valid = G[r + 1][c] in ["|", "L", "J"]
left_valid = G[r][c - 1] in ["-", "L", "F"]
assert sum([up_valid, right_valid, down_valid, left_valid]) == 2
if up_valid and down_valid:
G[r][c] = "|"
sd = 0
elif up_valid and right_valid:
G[r][c] = "L"
sd = 0
elif up_valid and left_valid:
G[r][c] = "J"
sd = 0
elif down_valid and right_valid:
G[r][c] = "F"
sd = 2
elif down_valid and left_valid:
G[r][c] = "7"
sd = 2
elif left_valid and right_valid:
G[r][c] = "-"
sd = 1
else:
assert False
# up right down left
DR = [-1, 0, 1, 0]
DC = [0, 1, 0, -1]
r = sr
c = sc
d = sd
dist = 0
while True:
dist += 1
r += DR[d]
c += DC[d]
if G[r][c] == "L":
if d not in [2, 3]:
break
elif d == 2:
d = 1
else:
d = 0
if G[r][c] == "J":
if d not in [1, 2]:
break
elif d == 1:
d = 0
else:
d = 3
if G[r][c] == "7":
# up right dswn left
if d not in [0, 1]:
break
elif d == 0:
d = 3
else:
d = 2
if G[r][c] == "F":
if d not in [0, 3]:
break
elif d == 0:
d = 1
else:
d = 2
assert G[r][c] != "."
if (r, c) == (sr, sc):
print(dist // 2)
break
R2 = 3 * R
C2 = 3 * C
G2 = [["." for _ in range(C2)] for _ in range(R2)]
for r in range(R):
for c in range(C):
if G[r][c] == "|":
G2[3 * r + 0][3 * c + 1] = "x"
G2[3 * r + 1][3 * c + 1] = "x"
G2[3 * r + 2][3 * c + 1] = "x"
elif G[r][c] == "-":
G2[3 * r + 1][3 * c + 0] = "x"
G2[3 * r + 1][3 * c + 1] = "x"
G2[3 * r + 1][3 * c + 2] = "x"
elif G[r][c] == "7":
G2[3 * r + 1][3 * c + 0] = "x"
G2[3 * r + 1][3 * c + 1] = "x"
G2[3 * r + 2][3 * c + 1] = "x"
elif G[r][c] == "F":
G2[3 * r + 2][3 * c + 1] = "x"
G2[3 * r + 1][3 * c + 1] = "x"
G2[3 * r + 1][3 * c + 2] = "x"
elif G[r][c] == "J":
G2[3 * r + 1][3 * c + 0] = "x"
G2[3 * r + 1][3 * c + 1] = "x"
G2[3 * r + 0][3 * c + 1] = "x"
elif G[r][c] == "L":
G2[3 * r + 0][3 * c + 1] = "x"
G2[3 * r + 1][3 * c + 1] = "x"
G2[3 * r + 1][3 * c + 2] = "x"
elif G[r][c] == ".":
pass
else:
assert False, G[r][c]
for row in G2:
# print(''.join(row))
pass
Q = deque()
SEEN = set()
for r in range(R2):
Q.append((r, 0))
Q.append((r, C2 - 1))
for c in range(C2):
Q.append((0, c))
Q.append((R2 - 1, c))
while Q:
r, c = Q.popleft()
if (r, c) in SEEN:
continue
if not (0 <= r < R2 and 0 <= c < C2):
continue
SEEN.add((r, c))
if G2[r][c] == "x":
continue
for d in range(4):
Q.append((r + DR[d], c + DC[d]))
ans = 0
for r in range(R):
for c in range(C):
seen = False
for rr in [0, 1, 2]:
for cc in [0, 1, 2]:
if (3 * r + rr, 3 * c + cc) in SEEN:
seen = True
if not seen:
ans += 1
print(ans)
|