Official
D - Ulam-Warburton Automaton Editorial
by
D - Ulam-Warburton Automaton Editorial
by
toam
\(i\) 回目の操作の \(T\) を \(T_i\) とします.このとき,以下が成り立ちます.
- 任意の \((x_1,y_1)\in T_{i+1}\) に対し,ある \((x_2, y_2)\in T_i\) が存在して \(|x_1-x_2|+|y_1-y_2|=1\) である.
- すなわち,\(i+1\) 回目に操作対象となるマスは,\(i\) 回目で操作したいずれかのマスに必ず隣接している.
よって,\(T_{i+1}\) を求めるためには,\(T_i\) のマスに隣接するマスのみを調べれば十分です.
\(T_i=\varnothing\) ならば \(T_{i+1}=\varnothing\) なので,\(T_i=\varnothing\) となったタイミングで探索を打ち切ってよいです.さらに, \(T_1, T_2, \ldots, \) は互いに素であるため,\(|T_1|+|T_2|+\ldots\leq HW\) です.よってこの問題は \(O(HW)\) で解くことができます.
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
dxdy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def in_grid(x, y):
return 0 <= x < H and 0 <= y < W
def count(x, y):
c = 0
for dx, dy in dxdy:
nx, ny = x + dx, y + dy
if in_grid(nx, ny) and S[nx][ny] == "#":
c += 1
return c
for i in range(H * W):
if i == 0:
T = []
for x in range(H):
for y in range(W):
if S[x][y] == "." and count(x, y) == 1:
T.append((x, y))
else:
nT = []
for x, y in T:
for dx, dy in dxdy:
nx, ny = x + dx, y + dy
if in_grid(nx, ny) and S[nx][ny] == "." and count(nx, ny) == 1:
nT.append((nx, ny))
T = nT
if len(T) == 0:
break
for x, y in T:
S[x][y] = "#"
ans = 0
for x in range(H):
for y in range(W):
ans += int(S[x][y] == "#")
print(ans)
posted:
last update: