lake_counting.py

# 水たまりのカウント
# 蟻本 p.35

lake = """\
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
W.W.W.....W.
.W.W......W.
..W.......W."""

lake = [list(l) for l in lake.split("\n")]

N = len(lake)
M = len(lake[0])

def dfs(y, x):
    lake[y][x] = '.'
    for dx in (-1, 0, 1):
        for dy in (-1, 0, 1):
            if (dx, dy) == (0, 0):
                continue
            nx = x + dx
            ny = y + dy
            if 0 <= ny < N and 0 <= nx < M:
                if lake[ny][nx] == 'W':
                    dfs(ny, nx)
            
def solve():
    res = 0
    for y in range(N):
        for x in range(M):
            if lake[y][x] == 'W':
               dfs(y, x)
               res += 1
    return res
 
ret = solve()
print(ret)