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