El problema Rotting Oranges es un clásico de entrevistas técnicas que combina matrices, propagación y búsqueda en anchura. Aquí entiendes qué pide el ejercicio, cómo se modela el cultivo y qué retos plantea para programadores que practican estructuras de datos.

¿Qué es el problema Rotting Oranges?

Es un ejercicio en el que recibes un cultivo representado como una matriz M por N. Cada celda puede contener uno de tres valores posibles que describen el estado de esa porción de tierra.

• 0: espacio vacío, sin planta.
• 1: planta de naranjas fresca.
• 2: planta de naranjas podrida.

Tu tarea es devolver el número de días que deben transcurrir hasta que ninguna celda contenga una naranja fresca. Si eso resulta imposible, retornas -1.

¿Qué representa cada número en la matriz de Rotting Oranges? El 0 es una celda vacía, el 1 es una naranja fresca y el 2 es una naranja podrida. La matriz simula un cultivo donde la podredumbre se propaga.

¿Cómo se propaga la podredumbre entre celdas adyacentes?

Una planta fresca se pudre cuando alguno de sus cuatro lados adyacentes (arriba, abajo, izquierda, derecha) contiene una planta ya podrida. La diagonal no cuenta.

El tiempo de contagio es exacto: un día por nivel de propagación. Si lo piensas como una plaga, tu planta sana se contamina al estar pegada a una infectada, y al día siguiente esa nueva infectada contamina a las suyas.

Y aquí viene lo interesante: el problema no se resuelve celda por celda en orden, sino por niveles de expansión. Cada día, todas las podridas actuales infectan a sus vecinas frescas al mismo tiempo. Eso es justo lo que modela una búsqueda en anchura o BFS.

¿Cómo se cuentan los días hasta que no queden naranjas frescas?

Imagina una matriz pequeña con varias naranjas frescas y una sola podrida en la esquina. El conteo arranca en cero y avanza así:

1. Día 1: la podrida inicial contagia a sus vecinas directas.
2. Día 2: esas nuevas podridas contagian a las suyas.
3. Día 3 y siguientes: la onda sigue expandiéndose hasta cubrir todo el cultivo alcanzable.

En el ejemplo de la clase, el cultivo termina completamente podrido en 4 días. Ese número es lo que retorna la función. Si al terminar la propagación queda al menos una naranja fresca aislada, el resultado es -1 porque ya no hay forma de rescatarla ni de contagiarla.

¿Cuándo se retorna -1 en Rotting Oranges? Cuando, después de propagar la podredumbre todo lo posible, todavía queda al menos una naranja fresca sin vecinos podridos que puedan alcanzarla.

¿Por qué importa el punto de inicio de la podredumbre?

El reto que plantea esta clase es de diseño. Si asumes que solo la naranja de la esquina empieza podrida, tu algoritmo es más simple: arrancas desde un único punto y propagas. Pero el problema real no garantiza esa condición.

En la práctica, puede haber varias naranjas podridas dispersas desde el día cero, y no puedes predecir dónde están. Eso cambia la estrategia: ya no basta con un punto de partida, necesitas procesarlas todas a la vez.

¿Qué estructura de datos conviene usar?

La pista está en la propagación por niveles. Una cola (queue) te permite registrar todas las naranjas podridas iniciales y procesarlas en bloques que representan días completos. Cada vuelta del ciclo equivale a un día de contagio.

• Recorres la matriz una vez para encontrar todas las celdas con valor 2.
• Las metes a la cola como puntos de partida simultáneos.
• Cuentas también cuántas naranjas frescas existen para validar al final si quedaron rezagadas.

Este recorrido inicial es clave: sin él, no sabes si retornar el conteo de días o -1.

¿Qué deberías cambiar en tu solución para casos generales?

Si tu primer intento asumió una sola naranja podrida en la esquina, el ajuste tiene tres frentes claros que vale la pena revisar antes de codificar.

• Procesa todas las naranjas podridas del estado inicial, no solo una.
• Lleva un contador de naranjas frescas para detectar el caso imposible.
• Maneja la propagación por niveles, no por celdas individuales, para que el conteo de días sea exacto.

Con esos tres cambios, tu solución pasa de resolver un caso particular a cubrir cualquier configuración del cultivo. Te invito a comentar qué estructura usarías tú, cómo manejarías el conteo de días y qué optimizaciones agregarías para matrices grandes.