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