C - Cross Editorial by evima
Another SolutionWe can count the “connected components” of black cells without paying much attention to the shape of the mark, utilizing the fact that the marks are separated. You would either perform Depth-First Search or use Union-Find. The size of a mark can be determined by dividing the number of cells by \(4\).
Sample Implementation (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)))
posted:
last update: