Ermitteln Sie den Durchmesser des Diagramms anhand der Suche nach Breitenpriorität (Python-Speicher).
Ich habe mich bei Qiita registriert, aber ich habe es nicht so oft benutzt, also werde ich es versuchen.
Zweck dieses Artikels
・ Persönliches Memo ・ Ich habe zuvor in Python nach einem Artikel über die Suche nach Breitenprioritäten gesucht, konnte ihn jedoch nicht finden. Daher möchte ich ihn für ähnliche Anfänger veröffentlichen. ・ Jemand kann Ihnen sagen, wie Sie besser schreiben können, wenn Sie hier schreiben
Fazit
- Der Durchmesser eines Diagramms, das verbunden ist und keine Seitenlänge hat, kann durch BFS (Breitenprioritätssuche) ermittelt werden. -Der Vorgang zum Abrufen des Elements vom Anfang der Liste ist langsam ・ Die Verwendung von Deque verbessert es jedoch ein wenig.
Zu lösendes Problem und Antwortpolitik
Problem
ABC151 D - Maze Master
Löse das. (ABCs D-Frage wird manchmal eine grafische Frage gegeben.) Bitte überprüfen Sie die Problemstellung unter dem Link.
Antwortrichtlinie
Interpretieren Sie es als Grafikproblem. Das Labyrinth wird durch einen verbundenen Graphen dargestellt, indem die benachbarten Scheitelpunkte oben, unten, links und rechts mit der Masse als Scheitelpunkt verbunden werden. Daher kann dieses Problem als "das Problem des Findens des Durchmessers eines Graphen angesehen werden, der verbunden ist und keine Seitenlänge hat". Hier ist der Durchmesser der Maximalwert des Abstands zwischen den Eckpunkten.
Was ist Breitenprioritätssuche (BFS)?
Weitere Informationen finden Sie in anderen Artikeln. Die Suche nach Breitenpriorität ist jedoch ein Algorithmus zum Auffinden einer erreichbaren Position von einem bestimmten Scheitelpunkt aus (nennen wir es Start).
Dieses Mal werde ich dies anwenden ** Finden Sie die maximale Entfernung vom Start **. Erstellen Sie zunächst eine Liste der Kanten, die mit jedem Scheitelpunkt verbunden sind, und geben Sie dann den Abstand vom Start in die vorbereitete Liste (Abstand) gemäß dem folgenden Flussdiagramm ein.
Wenn Sie den in diesem Flussdiagramm rot geschriebenen Teil "von Anfang an" in "vom Ende" ändern, wird dies zu einer Tiefenprioritätssuche (DFS). Der Durchmesser des Diagramms wird jedoch nicht von der DFS berechnet.
Suchvorgänge mit Breitenpriorität werden sofort zu den erreichbaren Scheitelpunkten verschoben, sodass kein Umweg erfolgt. Daher kann der kürzeste Abstand erhalten werden. Natürlich, es sei denn, die Seiten haben Länge.
Führen Sie dies schließlich für alle Scheitelpunkte des Diagramms aus und drucken Sie den größten der erhaltenen Werte aus, um den Vorgang abzuschließen.
H,W=[int(s) for s in input().split()]
maze=[input() for _ in range(H)]
edge=[set() for _ in range(H*W)]
n=0
numcount=0
for h in range(H):
for w in range(W):
if maze[h][w]=='#':
numcount+=1
n+=1
continue
if h>0 and maze[h-1][w]=='.':
edge[n].add(n-W)
if h<H-1 and maze[h+1][w]=='.':
edge[n].add(n+W)
if w>0 and maze[h][w-1]=='.':
edge[n].add(n-1)
if w<W-1 and maze[h][w+1]=='.':
edge[n].add(n+1)
n+=1
def dfs(start):
reach=[start]
distance=[-1 for _ in range(H*W)]
distance[n]=0
while reach:
_from=reach.pop(0)
for _to in edge[_from]:
if not(_to in reach) and distance[_to]==-1:
reach.append(_to)
distance[_to]=distance[_from]+1
return(max(distance))
n=0
ans=set()
for h in range(H):
for w in range(W):
if maze[h][w]=='.':
ans.add(dfs(n))
n+=1
print(max(ans))
Sie können jetzt AC.
Der Anfang der Liste ist langsam
Grundsätzlich ist das in Ordnung, aber ... Python ist ziemlich langsam und wird schnell zu TLE, wenn Sie nicht vorsichtig sind. Es ist besser, zeitaufwändige Vorgänge so weit wie möglich zu reduzieren. Das Abrufen eines Elements vom Anfang einer Liste ist beispielsweise sehr langsam.
import time
list_1=[i for i in range(100000)]
list_2=[i for i in range(100000)]
#Elemente von Anfang an extrahieren
start_1=time.time()
while list_1:
x=list_1.pop(0)
end_1=time.time()
#Elemente vom Ende extrahieren
start_2=time.time()
while list_2:
x=list_2.pop(-1)
end_2=time.time()
print('Von Anfang an:{}'.format(end_1-start_1))
#=>Von Anfang an: 1.4942412376403809
print('Vom Ende:{}'.format(end_2-start_2))
#=>Vom Ende: 0.014818668365478516
Obwohl ich die gleiche Operation mache, dauert es ungefähr 100 Mal länger, wenn ich das Element von Anfang an herausnehme. Diesmal war es in Ordnung, aber ich denke, es ist besser, Maßnahmen zu ergreifen, wenn viele ähnliche Operationen fortgesetzt werden.
benutze deque
Wenn Sie ein Element vom Anfang einer Liste abrufen, ist ein Typ namens deque hilfreich. Siehe hier für Details. Sammlungen --- Container-Datentyp (Python 3.7.3-Dokumentation)
Grob gesagt -Deque ist schnell, wenn Elemente vom Anfang oder Ende eines Arrays extrahiert werden ・ Die Liste ist schnell, wenn Sie aus der Mitte herausnehmen Es scheint so.
import time
from collections import deque
list_1=[i for i in range(100000)]
deq=deque([i for i in range(100000)])
#Beginnen Sie von vorne mit der Liste
start_1=time.time()
while list_1:
x=list_1.pop(0)
end_1=time.time()
#Beginnen Sie von vorne mit deque
start_3=time.time()
while deq:
x=deq.popleft()
end_3=time.time()
print('list：{}'.format(end_1-start_1))
#=>list：1.4939298629760742
print('deque：{}'.format(end_3-start_3))
#=>deque：0.009586334228515625
Es endete sehr früh. Das Problem ist diesmal, dass die Länge der Liste ungefähr 400 beträgt, so dass es keinen großen Unterschied macht (ziemlich langsam), aber je länger es ist, desto wahrscheinlicher ist es, dass es davon profitiert. Die Antwort mit deque lautet wie folgt.
from collections import deque
H,W=[int(s) for s in input().split()]
maze=[input() for _ in range(H)]
edge=[set() for _ in range(H*W)]
n=0
numcount=0
for h in range(H):
for w in range(W):
if maze[h][w]=='#':
numcount+=1
n+=1
continue
if h>0 and maze[h-1][w]=='.':
edge[n].add(n-W)
if h<H-1 and maze[h+1][w]=='.':
edge[n].add(n+W)
if w>0 and maze[h][w-1]=='.':
edge[n].add(n-1)
if w<W-1 and maze[h][w+1]=='.':
edge[n].add(n+1)
n+=1
def dfs(start):
reach=deque([start]) #Diese Zeile ändert sich
distance=[-1 for _ in range(H*W)]
distance[n]=0
while reach:
_from=reach.popleft() #Diese Zeile ändert sich
for _to in edge[_from]:
if not(_to in reach) and distance[_to]==-1:
reach.append(_to)
distance[_to]=distance[_from]+1
return(max(distance))
n=0
ans=set()
for h in range(H):
for w in range(W):
if maze[h][w]=='.':
ans.add(dfs(n))
n+=1
print(max(ans))
Zusammenfassung
Diesmal habe ich etwas über BFS gelernt. Um ehrlich zu sein, habe ich nicht bemerkt, dass der Durchmesser von BFS berechnet wurde, bis ich dieses Problem gelöst habe. Ich möchte versuchen, andere Grafikprobleme zu lösen und sie zu veröffentlichen, wenn ich Zeit habe.
Recommended Posts