I am studying for a competition professional. I have solved Lake Counting, which is famous for search problems, using Python, so I will post it. Many people solve it with a recursive function, but I solved it with a stack (recursive is not possible yet ...) Below is the implemented code. I've only tried two test cases, so I'm sorry if there are any patterns that I can't handle.
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)
It is written in the form of receiving standard input. Please point out any mistakes.
Recommended Posts