Submission #76261882

---

Source Code Expand

from collections import deque
from itertools import product

H, W = map(int, input().split())
S = [input() for i in range(H)]
if all("." not in s for s in S) or all("#" not in s for s in S):
    for _ in range(H):
        print("." * W)
    exit(0)
dp = [[None] * W for i in range(H)]
dq = deque()
for i, j in product(range(H), range(W)):
    if S[i][j] == "#":
        ok = False
        for di, dj in product(range(-1, 2), repeat=2):
            if di == dj == 0:
                continue
            ni, nj = i + di, j + dj
            if ni not in range(H):
                continue
            if nj not in range(W):
                continue
            if S[ni][nj] == ".":
                ok = True
        if ok:
            dp[i][j] = 0
            dq.append((i, j))
while dq:
    i, j = dq.popleft()
    for di, dj in product(range(-1, 2), repeat=2):
        if di == dj == 0:
            continue
        ni, nj = i + di, j + dj
        if ni not in range(H):
            continue
        if nj not in range(W):
            continue
        if dp[ni][nj] is None:
            dp[ni][nj] = dp[i][j] + 1
            dq.append((ni, nj))
for i in range(H):
    print("".join("#" if dp[i][j] % 2 == 0 else "." for j in range(W)))

Submission Info

Judge Result