Descripción del Problema

Dada una cuadrícula de dimensiones m x n, donde cada celda puede contenre:

• 0 para una celda vacía.
• 1 para una naranja fresca.
• 2 para una naranja podrida.

Cada minuto, las naranjas podridas infectan a las naranjas frescas adyacentes en las cuatro direcciones cradinales (arriba, abajo, izquierda, derecha). Se requiere determinar el tiempo mínimo necesario para que todas las naranjas frescas se pudran, o devolver -1 si no es posible.

Ejemplos Ilustrativos

Ejemplo 1:

Entrada: grid = [[2,1,1],[1,1,0],[0,1,1]]
Salida: 4

Ejemplo 2:

Entrada: grid = [[2,1,1],[0,1,1],[1,0,1]]
Salida: -1
Explicación: La naranja en la posición (2,0) nunca se pudre debido a la propagación restringida a cuatro direcciones.

Ejemplo 3:

Entrada: grid = [[0,2]]
Salida: 0
Explicación: No hay naranjas frescas al inicio, por lo que el tiempo es cero.

Enfoque de Solución: BFS Multi-fuente

La estrategia óptima es utilizar una Búsqueda en Amplitud (BFS) con múltiples orígenes. Esto implica:

• Enqueue todas las naranjas podridas iniciales como puntos de partida.
• Realizar expansiones nivel a nivel, donde cada nivel representa un minuto transcurrido.
• Para cada naranja podrida, explorar sus vecinos y marcarlos como podridos si están frescos.
• Usar un contador para registrar las naranjas frescas restantes y verificar si todas se infectan.

Implementación en Código

from collections import deque
from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        total_filas, total_columnas = len(grid), len(grid[0])
        cola_infeccion = deque()
        naranjas_frescas = 0

        # Identificar naranjas podridas iniciales y contar frescas
        for fila in range(total_filas):
            for columna in range(total_columnas):
                if grid[fila][columna] == 2:
                    cola_infeccion.append((fila, columna, 0))
                elif grid[fila][columna] == 1:
                    naranjas_frescas += 1

        minutos_totales = 0
        desplazamientos = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        # Propagar la infección mediante BFS
        while cola_infeccion:
            pos_x, pos_y, minuto_actual = cola_infeccion.popleft()
            minutos_totales = max(minutos_totales, minuto_actual)
            for delta_x, delta_y in desplazamientos:
                nueva_x, nueva_y = pos_x + delta_x, pos_y + delta_y
                if 0 <= nueva_x < total_filas and 0 <= nueva_y < total_columnas and grid[nueva_x][nueva_y] == 1:
                    grid[nueva_x][nueva_y] = 2
                    naranjas_frescas -= 1
                    cola_infeccion.append((nueva_x, nueva_y, minuto_actual + 1))

        return minutos_totales if naranjas_frescas == 0 else -1

Análisis de Complejidad

Puntos Críticos a Considerar

Relación con Otros Problemas

Este esquema de BFS multi-fuente es aplicable a problemas similares, tales como:

• Camino más corto en una matriz binaria.
• Flujo de agua en océanos Pacífico y Atlántico.
• Propagación de señales en redes espaciales.