Propagación de Plagas en Matrices usando BFS en Java

¿Cómo implementar la lógica para determinar los días necesarios para que todas las plantas se pudran?

En el apasionante mundo de la programación, solemos enfrentarnos a problemas de lógica que buscan desafiar nuestra capacidad de abstracción y resolución de problemas. Un ejemplo interesante es el cálculo de los días necesarios para que todas las plantas de un cultivo modelado como una matriz se pudran. A continuación, se explica cómo puedes abordar este problema utilizando el lenguaje de programación Java, aunque es posible adaptarlo a tu lenguaje de preferencia.

¿Cuál es el caso base?

Antes que nada, es importante definir los casos base para evitar operaciones innecesarias:

• Si la matriz cultivo es nula o no contiene valores, la respuesta será cero días, ya que no hay plantas que se puedan pudrir.

if (cultivo == null || cultivo.length == 0) return 0;

¿Por qué considerar frutas frescas?

El siguiente paso crucial es identificar las plantas frescas y podridas en el cultivo. Se utiliza un contador llamado cantidadFrescas que se incrementa por cada planta saludable:

int cantidadFrescas = 0;
for (int i = 0; i < cultivo.length; i++) {
    for (int j = 0; j < cultivo[i].length; j++) {
        if (cultivo[i][j] == 1) {
            cantidadFrescas++;
        }
    }
}

¿Cómo se utiliza BFS para la propagación?

La técnica de búsqueda por amplitud (BFS) es ideal para propagar el estado de podredumbre de una planta a sus adyacentes:

1. Inicialización de la cola: Comienza agregando todas las posiciones que contienen plantas ya podridas. Estas se identifican con el valor 2.

2. Direcciones posibles: Las direcciones definidas permiten expandirse a los vecinos (arriba, abajo, izquierda, derecha).

3. Iteración BFS: Mientras la cola no esté vacía, itera sobre los elementos:

Queue<int[]> cola = new LinkedList<>();
for (int i = 0; i < cultivo.length; i++) {
    for (int j = 0; j < cultivo[i].length; j++) {
        if (cultivo[i][j] == 2) {
            cola.offer(new int[]{i, j});
        }
    }
}

int[] direcciones = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!cola.isEmpty()) {
    int size = cola.size();
    for (int i = 0; i < size; i++) {
        int[] pos = cola.poll();
        int x = pos[0], y = pos[1];
        for (int[] dir : direcciones) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx >= 0 && ny >= 0 && nx < cultivo.length && ny < cultivo[0].length && cultivo[nx][ny] == 1) {
                cultivo[nx][ny] = 2; // Se pudrió
                cola.offer(new int[]{nx, ny});
                cantidadFrescas--;
            }
        }
    }
}

¿Cuándo paramos la búsqueda?

Es determinante parar la búsqueda cuando una de las siguientes situaciones se da:

• Todas las plantas están podridas: Si cantidadFrescas llega a cero tras el proceso, se retorna el contador de niveles o días menos uno, dado que el último incremento en el ciclo BFS no cuenta como día completo.

• Existen plantas que no pueden pudrirse: Retorna -1 en caso de que aún existan frutas frescas sin pudrirse al concluir BFS.

return (cantidadFrescas == 0) ? dias - 1 : -1;

¿Por qué es importante practicar y adaptar?

Es vital aplicar estos conceptos en tu lenguaje favorito, ejecutar pruebas y validar diferentes escenarios para captar la lógica; estrategias como compartir tus soluciones y analizar las de otros te permiten crecer y mejorar tus habilidades en programación.

En resumen, resolver este problema implica comprender y aplicar estructuras de datos adecuadas, como colas y listas enlazadas, junto con técnicas de búsqueda. Es una gran oportunidad para afianzar tus habilidades de resolución de problemas y lógica algorítmica. ¡Sigue practicando y retroalimentándote para crecer como desarrollador!