[PYTHON] [At Coder] Résolution d'un problème BFS typique [A - Darker and Darker]

[Ce site (version AtCoder! Arimoto (Débutant))](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) sert de référence pour résoudre le problème d'AtCoder et solidifier les bases de l'algorithme. La solution cette fois est AtCoder A - Darker and Darker. C'est un problème éducatif et typique de la recherche de priorité de largeur (BFS), qui est une sorte de recherche complète (semble-t-il). (Référence: blog de Kenchon)

problème

Les carrés peints en noir et blanc avec H lignes verticalement et W colonnes horizontalement sont indiqués. Lorsque vous peignez le haut, le bas, la gauche et la droite de tous les carrés noirs en noir en une seule opération, combien d'opérations peut-on effectuer pour peindre l'ensemble en noir? C'est le problème. 1 ≦ H ,W ≦ 1000

Solution

Dans le cas de ce problème ・ Problème pour trouver la valeur maximale de "la distance la plus courte du carré noir dans tous les carrés blancs" On peut le dire. En d'autres termes, il peut être considéré comme le problème d'itinéraire le plus court et résolu par BFS. C'est un bon problème qui permet de comprendre facilement l'image de la résolution avec BFS au lieu de DFS.

Il existe plusieurs positions de départ, mais le but est de les ajouter indépendamment à la file d'attente et d'utiliser BFS pour les rendre "simultanées".

• Il semble qu'un tel problème s'appelle "le problème de la route la plus courte avec plusieurs points". Il est également important de préparer une liste qui enregistre la distance par rapport au «carré noir au départ». (Initialisez tous les points de départ à 0)

[Note] En passant, si je changeais la file d'attente de liste en taple, le temps d'exécution était raccourci et la consommation de mémoire était également réduite.

from collections import deque

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

#Début noir('#')Distance de la position de
dist = [[-1]*W for _ in range(H)]

# '#'Ajouter la position de à la file d'attente (= Comme il y en a plusieurs cette fois, il y aura plusieurs départs)
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):
    """
Utilisez BFS pour trouver le nombre de fois où noircir tous les carrés
    
    Args:
        black_cells:File d'attente contenant les coordonnées du "carré noir au début" (plusieurs coordonnées disponibles)
        dist:Liste avec distance du "carré noir au début"[[-1, -1, 0], ...]
(La valeur initiale du carré blanc est 0)
        
    Returns:
        g:Nombre d'opérations répétées
    """
    d = 0
    while black_cells:
        #Pop car il est utilisé comme file d'attente()Pas 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:  #La cellule est blanche('.')Synonyme de
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

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