Ich studiere für einen Wettkampfprofi. Ich habe Lake Counting, das für Erkundungsprobleme bekannt ist, mit Python gelöst, also werde ich es hier posten. Die meisten Leute lösen es mit einer rekursiven Funktion, aber ich habe es mit einem Stapel gelöst (ich kann mich noch nicht zurückziehen ...) Unten ist der Code, den ich implementiert habe. Ich habe nur zwei Testfälle ausprobiert. Es tut mir leid, wenn es Muster gibt, mit denen ich nicht umgehen kann.
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)
Es wird in Form eines Empfangs von Standardeingaben geschrieben. Bitte weisen Sie auf Fehler hin.
Recommended Posts