Propagación de Plagas en Cultivos: Cálculo de Días para Contagio Total

¿Cómo resolver el problema de las naranjas podridas?

Imagina que tienes un campo de cultivo dividido en una matriz de M por N posiciones, y la idea es medir el tiempo necesario para que todas las naranjas frescas se pudran. Es un desafío intrigante, ¿verdad? Aquí te cuento cómo abordar este problema, popular en programaciones competitivas y algoritmos.

¿Cuál es el objetivo del problema?

Este reto consiste en determinar la cantidad mínima de días necesarios para que todas las naranjas frescas en el cultivo se vuelvan podridas, considerando que una naranja se pudre si alguna de sus vecinas (arriba, abajo, izquierda o derecha) está podrida. Si es imposible que todas las naranjas frescas se pudran, el resultado debe ser -1.

¿Cómo se definió la matriz?

La matriz M por N contempla tres posibles valores en cada celda:

• 0: Representa una celda vacía.
• 1: Indica una celda con una planta de naranjas frescas.
• 2: Indica una celda con una planta de naranjas podridas.

¿Cómo se propaga la podredumbre?

Cada día, cualquier planta fresca adyacente a una podrida se pudre. El desafío es calcular cuántos días tardará en pudrirse completamente todo el cultivo o identificar si alguna naranja nunca se pudrirá debido a un aislamiento inalterable.

Enfoque para resolver el problema

1. Modelar el problema: Considera la matriz como un grafo donde cada celda es un nodo. Este problema es análogo a una búsqueda en amplitud (BFS), empezando por todas las celdas con el valor 2.

2. Iniciar desde celdas podridas: Coloca todas las posiciones con naranjas podridas en una cola, ya que son tus puntos de partida para la propagación.

3. Simular la propagación:

   • Para cada nivel (cada día), procesa todas las celdas en la cola.
   • Añade las naranjas frescas adyacentes a una lista de celdas podridas para el siguiente día.
   • Llevar un conteo de días.

4. Verificar el resultado: Si después del proceso queda alguna naranja fresca, retorna -1. De lo contrario, el número de días es la solución.

¿Qué consideraciones especiales existen?

Este enfoque funciona bien bajo la presunción de que la implementación correcta de BFS asegurará que llegues al resultado más óptimo. Sin embargo, plantea interrogantes interesantes:

• ¿Qué pasa si solamente puedes empezar la propagación desde una esquina?
• Si la configuración de naranjas inicial es inédita, ¿cómo podrías prever la posición inicial óptima para la propagación?

¿Cómo optimizarías el algoritmo?

Una vez tienes el algoritmo básico, pensar en mejoras de eficiencia es crucial. Aquí algunas ideas:

• Optimización de memoria: Considera usar estructuras de datos eficientes, como arrays planos, para manejar la matriz.
• Paralelización: Si es posible, simula la propagación en paralelo para mejorar la velocidad, especialmente en matrices grandes.

Reflexiones finales

Este problema nos recuerda la importancia de modelar correctamente y abordar los problemas desde varias perspectivas. Te invito a dejar tus ideas sobre mejoras o adaptaciones de este algoritmo en la sección de comentarios del curso. ¡Estoy ansiosa por ver cómo lo resolverías tú y seguir aprendiendo juntos!