C - Cross 解説 by evima
別解印同士が離れていることを利用して、印の形状をあまり気にせずに黒マスの「連結成分」を数えることができます。深さ優先探索を行うか Union-Find を使うことになるでしょう。印のサイズは、マスの個数を \(4\) で割れば求められます。
実装例 (Python)
H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]
def dfs(y, x):
cnt = 1
C[y][x] = '.'
for dy in range(-1, 2):
for dx in range(-1, 2):
y2, x2 = y + dy, x + dx
if 0 <= y2 < H and 0 <= x2 < W and C[y2][x2] == '#':
cnt += dfs(y2, x2)
return cnt
ans = [0 for _ in range(min(H, W))]
for y in range(H):
for x in range(W):
if C[y][x] == '#':
ans[dfs(y, x) // 4 - 1] += 1
print(' '.join(map(str, ans)))
投稿日時:
最終更新: