クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-1 Lake Counting(POJ No.2386)」(p.35)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「2-1 Lake Counting(POJ No.2386)」(p.35)
のコードをPythonで書き直したものとなっています。

入力

N\,M\\(大きさ{N}\times{M}の庭)

入力例



10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.


解答

# 入力
N, M = map(int,input().split())
field = [list(input()) for _ in range(N)] # 庭

# 現在位置(x,y)
def dfs(x, y):
    # 今いるところを.に置き換える
    field[x][y] = '.'
    
    # 移動する8方向をループ
    for dx in range(-1, 2):
        for dy in range(-1, 2):
            # x方向にdx y方向にdy 移動した場所を(nx, ny)とする
            nx = x + dx
            ny = y + dy
            
            # nxとnyが庭の範囲内かどうかとfield[nx][ny]が水溜りかどうかを判定
            if 0 <= nx < N and 0 <= ny < M and field[nx][ny] == 'W':
                dfs(nx, ny)
    return

res = 0
for i in range(N):
    for j in range(M):
        if field[i][j] == 'W':
            # Wが残っているならそこからdfsをはじめる
            dfs(i, j)
            res += 1
print(res)