Resolver problemas de propagación en matrices es una habilidad fundamental en algoritmos y estructuras de datos. En esta implementación se utiliza BFS (Breadth-First Search) para simular cómo las naranjas podridas contagian a las frescas día a día, contando el tiempo mínimo necesario para que todo el cultivo se pudra. Aunque el código se desarrolla en Java, la lógica es aplicable a cualquier lenguaje.
¿Cómo manejar los casos base antes de ejecutar BFS?
Antes de lanzarse a recorrer la matriz, es imprescindible considerar casos especiales que evitan trabajo innecesario [0:37]:
- Si la matriz es nula o está vacía, se retorna cero porque no hay cultivo que procesar.
- Si al recorrer toda la matriz no se encuentra ninguna fruta fresca, significa que todas ya estaban podridas desde el inicio; se retorna cero sin necesidad de ejecutar BFS [4:28].
- Si tras la propagación completa aún quedan frutas frescas, significa que existían grupos aislados de plantas sanas sin conexión con ninguna podrida, separados por celdas vacías (valor cero). En ese caso se retorna menos uno para indicar que es imposible [1:20].
Estos casos son un ejemplo de lo que se conoce como validación de entradas: anticipar escenarios límite para hacer la solución más robusta y eficiente.
¿Cómo se estructura la cola y el recorrido por niveles?
Para implementar BFS se necesita una cola (queue), que en Java se representa con una LinkedList [2:22]. La cola almacena parejas de coordenadas (i, j) que representan posiciones en la matriz.
¿Cómo se inicializa la cola con las posiciones podridas?
Se recorre toda la matriz con un doble for, lo que implica una complejidad temporal de O(n²) [3:18]. Durante este recorrido:
- Si
cultivo[i][j] == 2, esa posición se agrega a la cola con cola.offer(new int[]{i, j}) [3:55].
- Si
cultivo[i][j] == 1, se incrementa el contador cantidadDeFrescas [4:08].
java
Queue<int[]> cola = new LinkedList<>();
int cantidadDeFrescas = 0;
for (int i = 0; i < cultivo.length; i++) {
for (int j = 0; j < cultivo[0].length; j++) {
if (cultivo[i][j] == 2) {
cola.offer(new int[]{i, j});
} else if (cultivo[i][j] == 1) {
cantidadDeFrescas++;
}
}
}
¿Por qué se itera hasta el tamaño actual de la cola y no hasta que esté vacía?
Aquí radica la clave del recorrido por niveles [7:02]. Un nivel equivale a un día de propagación. Dentro del while(!cola.isEmpty()), se captura el tamaño actual de la cola con cola.size() y se itera solo esa cantidad de veces. Los nuevos elementos agregados durante esa iteración pertenecen al siguiente nivel, es decir, al siguiente día.
java
int[][] direcciones = {{0,1},{0,-1},{1,0},{-1,0}};
int dias = 0;
while (!cola.isEmpty()) {
dias++;
int size = cola.size();
for (int i = 0; i < size; i++) {
int[] posActual = cola.poll();
for (int[] dir : direcciones) {
int x = posActual[0] + dir[0];
int y = posActual[1] + dir[1];
if (x >= 0 && x < cultivo.length && y >= 0 && y < cultivo[0].length && cultivo[x][y] != 2) {
cultivo[x][y] = 2;
cola.offer(new int[]{x, y});
cantidadDeFrescas--;
}
}
}
}
El arreglo de direcciones define los cuatro movimientos posibles: arriba, abajo, izquierda y derecha [5:52]. Si el problema requiriera propagación diagonal o en forma de L como el caballo de ajedrez, bastaría con agregar más parejas de coordenadas sin alterar la lógica central.
¿Cómo se validan los límites de la matriz al explorar adyacentes?
Antes de acceder a una posición vecina, se verifica que las coordenadas x y y no se salgan de los bordes de la matriz [8:37]. Esta validación de límites evita errores de tipo IndexOutOfBoundsException. Además, se comprueba que la celda no sea ya una naranja podrida (!= 2), porque no tiene sentido volver a procesarla.
Al final del algoritmo, el resultado depende de cantidadDeFrescas [10:30]:
- Si es cero, se retorna
dias - 1 porque el último incremento del contador no representa un día real de propagación.
- Si es diferente de cero, se retorna
-1 indicando que la propagación completa fue imposible.
La práctica de hacer pruebas de escritorio con diferentes entradas resulta esencial para comprender cómo fluyen los datos paso a paso. Probar con matrices donde todas están podridas, donde hay plantas aisladas o donde solo hay una planta fresca ayuda a validar cada rama condicional. Comparte tu implementación en tu lenguaje favorito y los casos de prueba que diseñaste para seguir aprendiendo en comunidad.
