0
0

More than 3 years have passed since last update.

Lake Counting(POJ NO.2386)をPython3で解く

Posted at

蟻本の練習問題初級編

競プロの勉強中の者です。
探索問題で有名なLakeCountingをPythonを使って解いたので載せます。
再帰関数で解く方が多いのですが、僕はスタックを使って解きました(再帰がまだできない...)
以下が実装したコードです。
テストケースを2通りしか試していないので、処理できないパターンがあったら申し訳ありません。

lakecounting.py
n,m=map(int,input().split())
field=[list(input()) for i in range(n)]
visited = [[0 for i in range(m)] for j in range(n)]
move = [[0,1],[1,0],[1,1],[0,-1],[-1,0],[-1,-1],[1,-1],[-1,1]]

cnt=0

for i in range(n):
    for j in range(m):
        if field[i][j] == "W" and visited[i][j]==0:
            sx,sy=i,j
            stack=[[sx,sy]]
            visited[sx][sy]=1
            while stack:
                x,y = stack.pop()
                for k in range(8):
                    nx,ny = x+move[k][0],y+move[k][1]
                    if 0<=nx<n and 0<=ny<m and visited[nx][ny]==0 and field[nx][ny]=="W":
                        stack.append([nx,ny])
                        visited[nx][ny]=1
            cnt += 1
print(cnt)

標準入力を受け取る形で書いています。
もし何か間違いがあればご指摘ください。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0