読者です 読者をやめる 読者になる 読者になる

PCC-35a : Lake Counting(POJ No.2386)

見方の説明

やってる事:C++のサンプルコードをPython(2.7.x)にて再実装
使用教材:プログラミングコンテストチャレンジブック(初版第3刷)
問題及びページ数:Lake Counting(POJ No.2386) - 35P

PCC35a.py

今回もDFSを使った処理となります。

#!/usr/bin/python
# -*- coding:utf-8 -*-

# input
n,m = map(int,raw_input().split())
a = []
for i in range(n) : 
    a.append(raw_input())

def solve():
    ret = 0
    for i in range(n) :
        for j in range(m) :
            if a[i][j] == 'W' :
                dfs(i,j)
                ret += 1
    
    print ret
    
def dfs(x, y):
    #  print "a[",x,"][",y,"]"
    if a[x][y] == 'W' :
        a[x] = a[x][:y] + "." + a[x][y+1:]
    
    for dx in range(-1,2) :
        for dy in range(-1,2) :
            nx = x + dx
            ny = y + dy
            if 0 <= nx and 0 <= ny and nx < n and ny < m and a[nx][ny] == 'W' :
                dfs(x+dx, y+dy)

if __name__ == "__main__" :
    solve()

システムテスト1

■testcase1

$ cat pcc-35a_testcase1
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W.....WW.
..W.......W.

■実行結果

$ python pcc-35a.py < pcc-35a_testcase1
3

システムテスト2

■testcase2

$ cat pcc-35a_testcase2
20 15
W........WW....
.WWW.....WWW.W.
....WW...WW...W
.........WW....
.........W.....
..W......W..W..
.W.W.....WW..W.
W.W.W.....W.W.W
.W.W.....WW..W.
..W.......W.W..
W........WW....
.WWW.....WWWWW.
....WW...WW...W
.........WW....
.........W.....
..W......W..W..
.W.W.....WW..W.
W.W.W.....W.W.W
.W.W.....WW..W.
..W.......W.W..

■実行結果

$ python pcc-35a.py < pcc-35a_testcase2
8