La partie 1 est facile.
La partie 2 est un problème sur les graphes et peut être obtenu en temps linéaire de la manière suivante.
On maintient un tableau deg qui pour chaque sommet associe le nombre de @ adjacents.
On maintient aussi une pile des sommets à traiter.
Pour chaque sommet v à traiter dans pile, et pour chaque voisin u de v, on décrémente deg[u] et si deg[u] == 3, on ajoute u à la pile.
En pseudo code ça donne ça
compteur = 0
pile = []
Calculer le tableau deg
pour chaque sommet v tel que grid[v] == @ et deg[v] <= 3
pile.push(v)
tant que pile non vide
v = pile.pop()
compteur += 1
pour chaque voisin u de v tel que grid[u] == @
deg[u] -= 1
si deg[u] == 3
pile.push(u)
renvoyer compteur
[^] # Re: Jour 4
Posté par Guillaume.B . En réponse au journal Advent of Code 2025. Évalué à 3.
La partie 1 est facile.
La partie 2 est un problème sur les graphes et peut être obtenu en temps linéaire de la manière suivante.
On maintient un tableau
degqui pour chaque sommet associe le nombre de @ adjacents.On maintient aussi une pile des sommets à traiter.
Pour chaque sommet
và traiter dans pile, et pour chaque voisinudev, on décrémentedeg[u]et sideg[u] == 3, on ajouteuà la pile.En pseudo code ça donne ça
160 microsecondes pour les deux parties