[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".

[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)

Recommended Posts

[At Coder] Résolution d'un problème BFS typique [A - Darker and Darker]
[At Coder] Résoudre les problèmes typiques de la recherche de priorité en profondeur (DFS)
[Python] AGC043A (problème de lecture et de DP) [At Coder]
Chez Coder (08/09/2020)
[Python] ABC133B (problème du triangle supérieur droit) [At Coder]
Problème de fractionnement typique de la combinaison de problèmes
[Chez Coder] Résoudre le problème de la dichotomie