[PYTHON] [Bei Coder] Lösen eines typischen BFS-Problems [A - Dunkler und Dunkler]

[Diese Site (AtCoder-Version! Arimoto (Anfänger))](https://qiita.com/drken/items/e77685614f3c6bf86f44#%E4%BE%8B%E9%A1%8C-2-5-5warshall-floyd -% E3% 82% 92% E4% BD% BF% E3% 81% 86% E5% 95% 8F% E9% A1% 8C) wird als Referenz verwendet, um das AtCoder-Problem zu lösen und die Grundlagen des Algorithmus zu festigen. Die Lösung ist diesmal AtCoders A - Dunkler und Dunkler. Es ist ein lehrreiches und typisches Problem der Breitenprioritätssuche (BFS), bei der es sich anscheinend um eine Art vollständige Suche handelt. (Referenz: Kenchons Blog)

Problem

Die schwarz-weiß gestrichenen Quadrate mit vertikalen H-Zeilen und horizontalen W-Spalten sind angegeben. Wie oft kann das Ganze beim Malen der oberen, unteren, linken und rechten Seite aller schwarzen Quadrate in einem Arbeitsgang in Schwarz gemalt werden? Ist das Problem. 1 ≦ H ,W ≦ 1000

Lösung

Im Falle dieses Problems ・ Problem, den Maximalwert "der kürzeste Abstand vom schwarzen Quadrat in allen weißen Quadraten" zu finden Es kann gesagt werden. Mit anderen Worten, es kann als das Problem der kürzesten Route angesehen und von BFS gelöst werden. Dies ist ein gutes Problem, da das Bild der Lösung mit BFS anstelle von DFS leicht zu verstehen ist.

Es gibt mehrere Startpositionen, aber der Punkt ist, sie unabhängig davon zur Warteschlange hinzuzufügen und BFS zu verwenden, um sie "gleichzeitig" zu machen.

• Es scheint, dass ein solches Problem "das kürzeste Straßenproblem mit mehreren Punkten" genannt wird. Es ist auch wichtig, eine Liste zu erstellen, in der der Abstand zum "schwarzen Quadrat am Anfang" aufgezeichnet wird. (Initialisieren Sie alle Startpunkte auf 0)

[Memo] Übrigens, wenn ich die Warteschlange von Liste auf Taple änderte, wurde die Ausführungszeit verkürzt und auch der Speicherverbrauch reduziert.

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

#Frühes Schwarz('#')Abstand von der Position von
dist = [[-1]*W for _ in range(H)]

# '#'Fügen Sie die Position von zur Warteschlange hinzu (= Da diesmal mehrere vorhanden sind, werden mehrere Starts durchgeführt.)
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
Verwenden Sie BFS, um zu ermitteln, wie oft alle Quadrate geschwärzt wurden
    
    Args:
        black_cells:Warteschlange mit den Koordinaten des "schwarzen Quadrats am Anfang" (mehrere Koordinaten verfügbar)
        dist:Liste mit Abstand zum "schwarzen Quadrat am Anfang"[[-1, -1, 0], ...]
(Der Anfangswert des weißen Quadrats ist 0)
        
    Returns:
        g:Anzahl der wiederholten Operationen
    """
    d = 0
    while black_cells:
        #Pop, da es als Warteschlange verwendet wird()Nicht popleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  #Die Zelle ist weiß('.')Synonym zu
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)