atcoder ABC 325　C - SensorsのPythonでの説明

DFS,BFS atcoder

atcoder.jp

・説明
　C - Cross
　の類題をもとにして解ける。この問題は隣接した'#'の数を求める問題なのでこの問題のDFSを今考えている問題のマス全てで行い、隣接する'#'の数をansにappendする。答えはlen(ans)になる。

import sys
sys.setrecursionlimit(10**6)

H,W=map(int,input().split())
map=[list(input()) for _ in range(H)]

#隣接した'#'の数を求めるDFS。
#例えばcnt += dfs(y2, x2)はy3, x3 = y2 + dy, x2 + dx,,,,とするとy3,x3までdfsじた場合、つまり#が3個のときはcnt=cnt+dfs(y2,x2) = cnt+cnt+dfs(y3,x3) = cnt+cnt+1 (return 1より) = 3となる(cnt=1より)。
def dfs(x, y):
    cnt=1
    if map[x][y] == "#":
        map[x][y] = "."
        
    for dx in range(-1,2):  
      for dy in range(-1,2): 
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and map[nx][ny] == "#":
            cnt+=dfs(nx,ny)
    return cnt

#ansに'#'の個数を入れていく。答えがlen(ans)になる。
ans=[]
for i in range(H):
    for j in range(W):
        if map[i][j]=='.':
            continue
        ans.append(dfs(i,j))
print(len(ans))