Rotting Oranges

+10

Recibes una cuadrícula como una lista de filas de igual longitud. Cada celda es 0 (vacía), 1 (una naranja fresca) o 2 (una naranja podrida). Cada minuto, cada naranja fresca que comparte un lado con una naranja podrida, arriba, abajo, a la izquierda o a la derecha, se pudre. Devuelve el número de minutos hasta que no quede ninguna naranja fresca, o -1 si alguna naranja fresca nunca puede pudrirse. Una cuadrícula sin naranjas frescas al inicio necesita 0 minutos.

Función

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

gridinteger-2d-array: la cuadrícula, una lista de 0, 1 y 2 por fila
Devuelveinteger: los minutos que faltan hasta que ninguna naranja esté fresca, o -1 si eso nunca ocurre

Restricciones

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Cada fila tiene la misma longitud.
Cada grid[i][j] es 0, 1 o 2.

Ejemplos

Entrada: grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
Salida: 6
Explicación: Al escribir las celdas como (fila, columna), la podredumbre comienza en (0,0) y sigue el único camino: (0,1) en el minuto 1, (0,2) y (1,1) en el minuto 2, (2,1) en el minuto 3, (2,0) y (2,2) en el minuto 4, (2,3) en el minuto 5. La naranja en (1,3) solo toca (2,3), así que es la última en estropearse, en el minuto 6.

+21 pruebas ocultas al enviar

Para ir más allá

Supón que cada naranja fresca necesita su propio número de minutos para pudrirse una vez que una naranja vecina se pudre. ¿Cómo encontrarías entonces el tiempo de finalización?

Solución

La descomposición comienza a la vez en cada naranja podrida y avanza una celda por minuto, así que la respuesta es una distancia: cuántos pasos separan a la naranja fresca más lejana de la naranja podrida más cercana. La búsqueda en anchura mide exactamente eso, si colocas todas las naranjas podridas en la cola antes de empezar y recorres la cola nivel por nivel, un minuto a la vez.

Simula minuto a minuto

Correcto, pero no termina con las pruebas más grandes

Intuición

Haz lo que dice el enunciado. Cada minuto, recorre toda la cuadrícula y enumera todas las naranjas frescas que estén junto a una podrida. Después pudre todas esas naranjas, suma uno al reloj y vuelve a recorrerla. Detente cuando un recorrido no encuentre nada que pudrir. Si en ese momento todavía queda una naranja fresca en la cuadrícula, la podredumbre nunca podrá alcanzarla: devuelve -1.

Primero enuméralas y después púdre las naranjas. Si pudres una naranja en mitad de un recorrido, una celda posterior del mismo recorrido la verá podrida y también se pudrirá; así, la podredumbre avanza varias celdas en un minuto y el reloj marca un tiempo demasiado bajo.

Esto es correcto, pero cada minuto requiere recorrer todas las filas × columnas de celdas, y el número de minutos puede acercarse al número de celdas. En una cuadrícula de 150 × 150 cuyas naranjas frescas forman un único camino sinuoso con la podredumbre en un extremo, la podredumbre necesita 11,324 minutos: 11,324 recorridos de 22,500 celdas, unos 2.5 × 10^8 comprobaciones de celdas, casi todas en celdas que no pueden cambiar.

Algoritmo

Establece los minutos en 0.
Recorre la cuadrícula y enumera cada naranja fresca que tenga una vecina podrida.
Si la lista está vacía, detente. De lo contrario, convierte en podridas todas las naranjas de la lista, suma 1 a los minutos y vuelve a recorrerla.
Devuelve -1 si queda alguna naranja fresca; de lo contrario, devuelve los minutos.

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

BFS de múltiples fuentes por niveles

Intuición

El recorrido pierde tiempo en celdas alejadas de la acción. Las únicas naranjas que pueden pudrirse en el minuto t+1 son las vecinas frescas de las naranjas que se pudrieron en el minuto t. Así que guarda exactamente esas en una cola: la frontera de la podredumbre.

Inicia la cola con todas las naranjas podridas en el minuto 0, todas juntas. Esa es la parte de múltiples fuentes. Una naranja fresca se pudre en el minuto igual a su distancia de la naranja podrida más cercana, y una búsqueda en anchura iniciada con todas las fuentes llega primero a cada celda desde la fuente que esté más cerca. Una búsqueda hace el trabajo de una búsqueda por fuente y de tomar el mínimo.

Después, trabaja por niveles. Al comienzo de un minuto, la cola contiene k naranjas, las que se pudrieron el último minuto. Saca exactamente k del frente; por cada una, pudre sus vecinas frescas y añádelas al final. Cuando terminas con las k, ha pasado un minuto y la cola contiene la siguiente frontera. En el primer ejemplo, los niveles son {(0,0)}, {(0,1)}, {(0,2), (1,1)}, {(2,1)}, {(2,0), (2,2)}, {(2,3)}, {(1,3)}: seis pasos después del inicio, así que son seis minutos.

Cuenta las naranjas frescas una vez al inicio y reduce el recuento cada vez que una se pudre. Detente en cuanto llegue a 0; de lo contrario, el último nivel sumaría un minuto en el que no se pudre nada. Devuelve -1 si la cola se vacía mientras el recuento es mayor que 0. Cada celda entra en la cola como máximo una vez y comprueba cuatro vecinas, así que el trabajo es O(rows × cols).

Algoritmo

Pon cada naranja podrida en una cola y cuenta las naranjas frescas.
Establece los minutos en 0. Mientras la cola no esté vacía y queden naranjas frescas, suma 1 a los minutos y anota el tamaño k de la cola.
Saca k naranjas del frente. Para cada vecina fresca dentro de la cuadrícula, márcala como podrida, reduce el recuento de naranjas frescas y añádela al final.
Cuando termine el bucle, devuelve los minutos si el recuento de naranjas frescas es 0; de lo contrario, devuelve -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

Errores comunes y casos límite

La mayoría de las respuestas incorrectas aquí se equivocan por un minuto o se deben a que la búsqueda empieza en el lugar equivocado.

Contar un minuto para el último nivel. Si el bucle se ejecuta hasta que la cola queda vacía, su última pasada no pudre nada y aun así suma 1. Detente en cuanto no quede ninguna naranja fresca.
Buscar desde cada naranja podrida por turnos. La primera búsqueda reclama todas las naranjas a las que llega según su propio reloj, así que dos fuentes que deberían encontrarse en el medio dan un tiempo demasiado alto: [[2, 1, 1, 1, 1, 1, 1, 2]] tarda 3 minutos, no 6.
Pudrir las naranjas durante el recorrido en la versión minuto a minuto. Una celda que aparece más adelante en el mismo recorrido las ve entonces como podridas, y la podredumbre cruza varias celdas en un minuto.
Devolver -1 porque no hay ninguna naranja podrida. Si tampoco hay naranjas frescas, no tiene que ocurrir nada: [[0]] devuelve 0. Solo las naranjas frescas que nunca se pudren hacen que la respuesta sea -1.
Marcar una naranja como podrida al sacarla de la cola en vez de al añadirla. Entonces, una naranja junto a dos podridas se añade dos veces y el recuento de naranjas frescas baja de cero.
Búsqueda en profundidad. Sigue un camino hasta donde pueda llegar, así que la primera vez que alcanza una naranja no indica nada sobre el minuto en que esa naranja se pudre.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Rotting Oranges?

O(rows × cols) con búsqueda en anchura. El primer recorrido examina cada celda una vez, y cada naranja entra en la cola como máximo una vez y comprueba cuatro vecinos. La cola ocupa O(rows × cols) de espacio en el peor caso: una cuadrícula llena de naranjas podridas.

¿Por qué usar BFS y no DFS para las naranjas podridas?

La búsqueda en anchura visita las celdas según su distancia desde el inicio, y aquí la distancia equivale al tiempo: el nivel k de la búsqueda es exactamente el conjunto de naranjas que se pudren en el minuto k. La búsqueda en profundidad puede llegar a una celda por un desvío largo antes de encontrar la ruta corta, así que tendría que volver a visitar las celdas cada vez que encuentra una ruta más corta.

¿Qué es la búsqueda en anchura de múltiples fuentes?

Una búsqueda en anchura que comienza con varias celdas en la cola a distancia 0 en lugar de una. En una sola pasada, asigna a cada celda su distancia a la fuente más cercana; da el mismo resultado que una búsqueda por fuente tomando el mínimo, con el coste de una sola búsqueda. Se usa para cualquier pregunta sobre «la distancia al X más cercano» en una cuadrícula.

¿Puedes resolver el problema de las naranjas podridas sin cambiar la cuadrícula?

Sí. Mantén un arreglo separado para las celdas visitadas y consúltalo en lugar de escribir 2 en la cuadrícula. Eso cuesta O(rows × cols) de memoria adicional, que la cola puede necesitar de todos modos. En los lenguajes que pasan la cuadrícula por referencia, escribir en ella también modifica la cuadrícula del código que la llama, algo sobre lo que un entrevistador podría preguntarte.

Python

def orangesRotting(grid):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado