J'étudie pour un professionnel de la compétition. J'ai résolu le comptage des lacs, célèbre pour ses problèmes d'exploration, en utilisant Python, donc je le posterai ici. La plupart des gens le résolvent avec une fonction récursive, mais je l'ai résolu avec une pile (je ne peux pas encore reculer ...) Voici le code que j'ai implémenté. Je n'ai essayé que deux cas de test, donc je suis désolé s'il y a des modèles que je ne peux pas gérer.
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)
Il est écrit sous la forme de réception d'une entrée standard. Veuillez signaler toute erreur.
Recommended Posts