#蟻本の練習問題初級編
競プロの勉強中の者です。
探索問題で有名な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)
標準入力を受け取る形で書いています。
もし何か間違いがあればご指摘ください。