AtCoder Beginner Contest 300 - C

問題
https://atcoder.jp/contests/abc300/tasks/abc300_c

概要
グリッドCに書かれている#について、X型のサイズ毎の個数を全て出力します。

解法
縦Hマス、横Wマスの全てのマスについて全探索します。
#があるマスを見つけたら、左上、右上、左下、右下の4方向をチェックして、
さらに#のマスを見つけるという形でDFSによる探索をします。
Xのかたまりに含まれる#の個数とサイズは以下のようになっているので、
1度のDFSで探索できたマスから、サイズを特定すればよいです。

#	サイズ
5	1
9	2
4n+1	n

ソースコード

abc300c.py

h, w = map(int, input().split())
c = [list(input()) for i in range(h)]

# サイズnの個数を初期化
n = min(h, w)
ans = [0 for i in range(n + 1)]

g_cnt = 0

def dfs(sx, sy):
	global g_cnt
	c[sx][sy] = '.'
	g_cnt += 1

	dx = [-1, -1, 1, 1]
	dy = [-1, 1, -1, 1]
	# 4方向探索
	for i in range(4):
		nx = sx + dx[i]
		ny = sy + dy[i]
		# 移動条件チェック
		if(nx < 0 or nx >= h): continue
		if(ny < 0 or ny >= w): continue
		if(c[nx][ny] == '.'): continue
		dfs(nx, ny)

# 全てのマス探索
for i in range(h):
	for j in range(w):
		if c[i][j] != '#': continue
		# 毎回初期化する
		g_cnt = 0
  
		# dfs
		dfs(i, j)

		# サイズ取得
		sz = (g_cnt - 1) // 4
		ans[sz] += 1

# 出力
for i in range(1, n+1):
	print(str(ans[i]) + str(" "), end="")
print()