Rotting Oranges

+10

Vous recevez une grille sous forme de liste de lignes de même longueur. Chaque cellule contient 0 (vide), 1 (une orange fraîche) ou 2 (une orange pourrie). Chaque minute, chaque orange fraîche qui partage un côté avec une orange pourrie, en haut, en bas, à gauche ou à droite, pourrit. Retournez le nombre de minutes jusqu’à ce qu’il ne reste plus aucune orange fraîche, ou -1 si certaines oranges fraîches ne peuvent jamais pourrir. Une grille ne contenant aucune orange fraîche au départ nécessite 0 minute.

Fonction

orangesRotting(grid: integer-2d-array) → integer

gridinteger-2d-array: la grille, une liste de 0, 1 et 2 par ligne
Renvoieinteger: le nombre de minutes jusqu’à ce qu’il n’y ait plus d’orange fraîche, ou -1 si cela n’arrive jamais

Contraintes

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Chaque ligne a la même longueur.
Chaque grid[i][j] vaut 0, 1 ou 2.

Exemples

Entrée: grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
Sortie: 6
Explication: En écrivant les cellules sous la forme (ligne, colonne), la pourriture quitte (0,0) et suit le seul chemin : (0,1) à la minute 1, (0,2) et (1,1) à la minute 2, (2,1) à la minute 3, (2,0) et (2,2) à la minute 4, (2,3) à la minute 5. L’orange en (1,3) ne touche que (2,3) ; c’est donc la dernière à pourrir, à la minute 6.

+21 tests cachés à la soumission

Pour aller plus loin

Supposons que chaque orange fraîche ait besoin de son propre nombre de minutes pour pourrir une fois qu’une orange voisine est pourrie. Comment trouverais-tu alors le temps nécessaire pour que toutes les oranges pourrissent ?

Solution

La pourriture se propage simultanément à partir de chaque orange pourrie et avance d’une cellule par minute. La réponse est donc une distance : combien d’étapes séparent l’orange fraîche la plus éloignée de l’orange pourrie la plus proche. Le parcours en largeur mesure exactement cela, si tu places toutes les oranges pourries dans la file avant de commencer et que tu traites la file niveau par niveau, une minute à la fois.

Simuler minute par minute

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Fais ce que raconte l’énoncé. À chaque minute, parcours toute la grille et dresse la liste de chaque orange fraîche qui touche une orange pourrie. Puis fais pourrir toutes ces oranges, ajoute 1 à l’horloge et parcours de nouveau la grille. Arrête-toi quand un parcours ne trouve rien à faire pourrir. S’il reste alors une orange fraîche dans la grille, la pourriture ne pourra jamais l’atteindre : renvoie -1.

Dresse d’abord la liste, puis fais pourrir les oranges. Si tu fais pourrir une orange au milieu d’un parcours, une case examinée plus tard au cours du même parcours la voit comme pourrie et fait pourrir l’orange à son tour ; la pourriture parcourt alors plusieurs cases en une minute et le temps obtenu est trop faible.

Cette méthode est correcte, mais chaque minute nécessite de parcourir toutes les lignes × colonnes de la grille, et le nombre de minutes peut approcher le nombre de cases. Sur une grille de 150 × 150 dont les oranges fraîches forment un chemin sinueux avec la pourriture à son extrémité, la pourriture met 11,324 minutes : 11,324 parcours de 22,500 cases, soit environ 2.5 × 10^8 vérifications de cases, presque toutes sur des cases qui ne peuvent pas changer.

Algorithme

Définissez les minutes à 0.
Parcourez la grille et listez chaque orange fraîche qui a un voisin pourri.
Si la liste est vide, arrêtez-vous. Sinon, transformez chaque orange listée en orange pourrie, ajoutez 1 aux minutes et parcourez à nouveau la grille.
Renvoyez -1 s’il reste une orange fraîche, sinon les minutes.

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    minutes = 0
    while True:
        # Find every fresh orange that touches a rotten one right now.
        to_rot = []
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != 1:
                    continue
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 2:
                        to_rot.append((r, c))
                        break
        if not to_rot:
            break
        # Rot them only after the scan, so the rot moves one step a minute.
        for r, c in to_rot:
            grid[r][c] = 2
        minutes += 1
    for row in grid:
        if 1 in row:
            return -1
    return minutes

Parcours BFS multi-source par niveaux

Intuition

Le parcours perd du temps sur des cellules éloignées de l’action. Les seules oranges qui peuvent pourrir à la minute t+1 sont les oranges fraîches voisines de celles qui ont pourri à la minute t. Il suffit donc de les garder dans une file : la frontière de la pourriture.

Commence par mettre dans la file toutes les oranges pourries à la minute 0, toutes ensemble. C’est l’aspect multi-source. Une orange fraîche pourrit à la minute correspondant à sa distance de l’orange pourrie la plus proche, et une recherche en largeur lancée depuis toutes les sources atteint chaque cellule d’abord depuis la source la plus proche. Une seule recherche fait le travail d’une recherche par source, puis du calcul du minimum.

Traite ensuite les niveaux. Au début d’une minute, la file contient k oranges, celles qui ont pourri à la minute précédente. Retire exactement k oranges du début de la file ; pour chacune, fais pourrir ses voisines fraîches et ajoute-les à la fin. Une fois les k oranges traitées, une minute s’est écoulée et la file contient la frontière suivante. Dans le premier exemple, les niveaux sont {(0,0)}, {(0,1)}, {(0,2), (1,1)}, {(2,1)}, {(2,0), (2,2)}, {(2,3)}, {(1,3)} : six étapes après le début, donc six minutes.

Compte les oranges fraîches une seule fois au début et décrémente le compteur chaque fois qu’une orange pourrit. Arrête-toi dès qu’il atteint 0 ; sinon, le dernier niveau ajouterait une minute pendant laquelle rien ne pourrit. Renvoie -1 si la file se vide alors que le compteur est supérieur à 0. Chaque cellule entre dans la file au plus une fois et vérifie quatre voisines, donc le travail est en O(rows × cols).

Algorithme

Placez chaque orange pourrie dans une file d’attente et comptez les oranges fraîches.
Définissez le nombre de minutes sur 0. Tant que la file d’attente n’est pas vide et qu’il reste des oranges fraîches, ajoutez 1 au nombre de minutes et notez la taille k de la file.
Retirez k oranges au début de la file. Pour chaque voisine fraîche dans la grille, marquez-la comme pourrie, diminuez le nombre d’oranges fraîches et ajoutez-la à la fin de la file.
Lorsque la boucle se termine, renvoyez le nombre de minutes si le nombre d’oranges fraîches est égal à 0, sinon -1.

from collections import deque


def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # Every orange that is rotten at minute 0 starts in the queue.
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:
        minutes += 1
        # The queue holds exactly the oranges that went rotten last minute.
        # Rot their fresh neighbours; those become the next minute's queue.
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

Pièges et cas limites

La plupart des mauvaises réponses ici sont décalées d’une minute ou viennent d’un départ de la recherche au mauvais endroit.

Compter une minute pour le dernier niveau. Si la boucle continue jusqu’à ce que la file soit vide, son dernier passage ne fait pourrir aucune orange et ajoute quand même 1. Arrête-toi dès qu’il ne reste plus d’orange fraîche.
Lancer la recherche à partir de chaque orange pourrie, à tour de rôle. La première recherche s’approprie chaque orange qu’elle atteint avec son propre compteur, donc deux sources qui devraient se rejoindre au milieu donnent un temps trop élevé : [[2, 1, 1, 1, 1, 1, 1, 2]] prend 3 minutes, pas 6.
Faire pourrir des oranges pendant le parcours dans la version minute par minute. Une cellule parcourue plus tard au cours du même balayage les voit alors comme pourries, et la pourriture traverse plusieurs cellules en une minute.
Renvoyer -1 parce qu’il n’y a aucune orange pourrie. S’il n’y a pas non plus d’orange fraîche, rien ne doit se passer : [[0]] renvoie 0. Seules les oranges fraîches qui ne pourrissent jamais donnent une réponse de -1.
Marquer une orange comme pourrie quand tu la retires de la file au lieu de le faire quand tu l’y ajoutes. Une orange à côté de deux oranges pourries est alors ajoutée deux fois, et le nombre d’oranges fraîches devient négatif.
La recherche en profondeur d’abord. Elle suit un chemin aussi loin que possible, donc le premier moment où elle atteint une orange ne dit rien sur la minute où cette orange pourrit.

Questions fréquentes4

Quelle est la complexité temporelle du problème des oranges pourries ?

O(rows × cols) avec une recherche en largeur. Le premier parcours examine chaque cellule une fois, et chaque orange entre dans la file au plus une fois et vérifie quatre voisines. Dans le pire des cas, la file occupe un espace de O(rows × cols), lorsque la grille est entièrement remplie d’oranges pourries.

Pourquoi utiliser BFS plutôt que DFS pour le problème des oranges pourries ?

La recherche en largeur visite les cellules selon leur distance par rapport au départ, et ici, la distance correspond au temps : le niveau k de la recherche est exactement l’ensemble des oranges qui pourrissent à la minute k. La recherche en profondeur peut atteindre une cellule en empruntant un long détour avant de trouver le chemin le plus court ; elle devrait donc revisiter les cellules chaque fois qu’elle en trouve un plus court.

Qu’est-ce qu’un BFS multi-source ?

Un parcours en largeur qui commence avec plusieurs cellules dans la file à la distance 0 au lieu d’une seule. En un seul passage, il donne à chaque cellule sa distance par rapport à la source la plus proche, soit le même résultat qu’une recherche par source en prenant le minimum, pour le coût d’une seule recherche. Toute question portant sur la « distance jusqu’au X le plus proche » sur une grille utilise cette méthode.

Peux-tu résoudre le problème des oranges pourries sans modifier la grille ?

Oui. Gardez un tableau séparé des cases visitées et vérifiez-le au lieu d’écrire 2 dans la grille. Cela coûte O(rows × cols) de mémoire supplémentaire, dont la file peut de toute façon avoir besoin. Dans les langages qui passent la grille par référence, y écrire modifie également la grille de l’appelant, ce qu’un recruteur pourrait vous demander d’expliquer.

Python

def orangesRotting(grid):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]

Attendu