Resolución de Rotting Oranges usando BFS

Clase 27 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles

Resumen

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

El cultivo de naranjas podridas es un desafío que exige lógica y estrategias de programación eficientes. Imagina tener un campo representado por una matriz con valores: 0 (espacios vacíos), 1 (naranjas frescas) y 2 (naranjas podridas). El objetivo es determinar cuántos días son necesarios para que todas las naranjas frescas se pudran bajo las condiciones de contagio establecido, con el enfoque puesto principalmente en las técnicas de BFS (Breadth-First Search).

¿Cómo se propaga la "plaga" de naranjas podridas?

La propagación sigue una dinámica similar a una cadena de contagios. Cada día, las naranjas podridas "infectan" a sus vecinas adyacentes (arriba, abajo, izquierda, derecha), cambiando su estado de 1 a 2. Este requerimiento es vital en la resolución del problema, ya que debes identificar y contar cuántos días pasan hasta que se alcance una saturación total de naranja podrida.

Ejemplo de propagación:

Día 0: Inicia con una matriz de naranjas podridas en ciertas posiciones solamente.
Día 1: Todas las naranjas adyacentes a las podridas comienzan a pudrirse.
Día 2 en adelante: El proceso se repite hasta que no queden naranjas frescas.

¿Qué técnica de programación se debe utilizar?

La técnica ideal para abordar este problema es BFS. Al igual que una plaga que se propaga por niveles, BFS te permite avanzar de manera uniforme por cada nivel (día), asegurando que examines todas las naranjas de igual manera.

Pasos para implementar la solución con BFS:

Identificar nodos iniciales: Considerar las posiciones iniciales de las naranjas podridas en la matriz.
Utilizar una cola: Esta estructura te ayuda a procesar las naranjas que se pudrirán en los días siguientes, manteniendo el orden necesario.
Registro de casillas visitadas: Emplear un hash set para evitar el procesamiento de posiciones ya podridas.
Calcular los niveles: Al finalizar, el número de niveles recorridos en el BFS equivaldrá al número de días necesarios para pudrir toda la matriz.

¿Por qué usar un hash set?

Usar un hash set es crucial para la eficiencia del programa. Permite verificar si una posición ya fue visitada o no en tiempo constante (O(1)), evitando así procesos redundantes que incrementan el tiempo de ejecución hasta (O(n)) si se usara una lista regular.

¿Cuáles son posibles limitaciones y consideraciones?

Este enfoque podría no ser óptimo si el cultivo está completamente compuesto por naranjas frescas al inicio, pues no habría ninguna naranja podrida para empezar el contagio. Sin embargo, asumiendo que siempre hay al menos una naranja podrida, el BFS garantiza un análisis ordenado y exhaustivo.

Un detalle importante para considerar es que la solución podría variarse potencialmente usando DFS (Depth-First Search), pero BFS es más natural debido al comportamiento de propagación uniforme a través de niveles, lo que facilita contar los días.

Continúa explorando alternativas y desafía tu conocimiento: ¿puede el DFS competir en eficiencia?, ¿qué mejoras potenciales imaginas implementar? ¡La curiosidad y análisis crítico son tus mejores aliados en la programación!

Carlos Perilla

student•

Se me ocurre como solución al problema, analizar a partir de "radios" de infección de cada naranja, así podemos determinar por medio de matemáticas cuanto tardaría en infectar todo el campo una naranja podrida.

Luego podríamos comparar el tiempo mínimo de infección entre todas las naranjas podridas, y hacer algún calculo de densidad. Por ejemplo si hay densidad de naranjas podridas en una sola esquina del campo, podríamos asumir, que con el primer calculo es suficiente.

Pero si la densidad no es homogénea (es decir no están en una sola esquina, sino dispersas), podríamos hacer un análisis más profundo y ver cuando reduce en días, el resultado obtenido previamente.

Esa es una idea que se me ocurre que podría ser computacionalmente más económica, aunque atenida a ciertas condiciones, por ejemplo conocer las posiciones de antemano (en una lista) de las naranjas podridas, y contar con un campo finito.

Mario Alberto Hernández Pintor

student•

Bryan Castano

student•

Hola Chicos \n

Yo estoy buscando my Solucion por Breadth First SeRCH 'BFS' . Yo tengo este Algoritmo que me hice guidado de un tutorial Podcast de Youtube meses atras. \nally se implementa Queue paea soportar la busqueda pro anchura de la Grid de una matrix en Adyacencia.

Yo no he dado con la solucion aun\n pero cerca estoy \n yo he visto que la queue ( ) es bien importante asi como isVisisted() \n

Este problema tambien se debe solucionar por Matrix de adyacencia\n ademas { 1, 0 } existe valores en '2' que representan lo 'rotten Orange ' por tanto unicamente faltase uun condicional dponde compruebe ( arr[ node ][index ] == '2' dentro de mi inner for loop \n

#include <iostream>
#define size 36
#define V 6
using namespace std;

int Queue[size];

int front = 0;
int rear = 0;

int isQueueEmpty() 
{

    if(front == rear)
    
        return 1;
        
    return 0;
}

int dequeue()
{
    if(front == rear)
    
        return -1;
        
    else 
    {
        int temp = Queue[front];
        front++;
        
        return temp;
        
    }
}

void enqueue(int val)
{
    if(rear == size)
        return;
    else 
    {
        Queue[rear] = val;
        rear++;
    }
}

void bfs(int arr[V][V], int source)
{
    int isVisited[V] = {0};
    int index;
    
    enqueue(source);
    isVisited[source] = 1;
    
    while(!isQueueEmpty())
    {
        int node = dequeue();
        cout<<"Visited Node : "<<node<<endl;
        
        for(index = 0; index < V; index++)
        {
            if(arr[node][index] == 1 && isVisited[index] == 0)
            {
                enqueue(index);
                isVisited[index] = 1;
            }
        }
        
    }
    for ( int i = 0; i< V ; i ++ ) {

        cout << isVisited[i] << "\t" ;
    }
    cout << "\n";
    
}

```#include \<iostream>

\#define size 36

\#define V 6

using namespace std;



int Queue\[size];



int front = 0;

int rear = 0;



int isQueueEmpty()&#x20;

{



&#x20;   if(front == rear)

&#x20;  &#x20;

&#x20;       return 1;

&#x20;      &#x20;

&#x20;   return 0;

}



int dequeue()

{

&#x20;   if(front == rear)

&#x20;  &#x20;

&#x20;       return -1;

&#x20;      &#x20;

&#x20;   else&#x20;

&#x20;   {

&#x20;       int temp = Queue\[front];

&#x20;       front++;

&#x20;      &#x20;

&#x20;       return temp;

&#x20;      &#x20;

&#x20;   }

}



void enqueue(int val)

{

&#x20;   if(rear == size)

&#x20;       return;

&#x20;   else&#x20;

&#x20;   {

&#x20;       Queue\[rear] = val;

&#x20;       rear++;

&#x20;   }

}



void bfs(int arr\[V]\[V], int source)

{

&#x20;   int isVisited\[V] = {0};

&#x20;   int index;

&#x20;  &#x20;

&#x20;   enqueue(source);

&#x20;   isVisited\[source] = 1;

&#x20;  &#x20;

&#x20;   while(!isQueueEmpty())

&#x20;   {

&#x20;       int node = dequeue();

&#x20;       cout<<"Visited Node : "<\<node<\<endl;

&#x20;      &#x20;

&#x20;       for(index = 0; index < V; index++)

&#x20;       {

&#x20;           if(arr\[node]\[index] == 1 && isVisited\[index] == 0)

&#x20;           {

&#x20;               enqueue(index);

&#x20;               isVisited\[index] = 1;

&#x20;           }

&#x20;       }

&#x20;      &#x20;

&#x20;   }

&#x20;   for ( int i = 0; i< V ; i ++ ) {



&#x20;       cout << isVisited\[i] << "\t" ;

&#x20;   }

&#x20;   cout << "\n";

&#x20;  &#x20;

}

Yojan Antonio Pardo Zabala

student•

Tambien se puede resolver con DFS, la complejidad temporal creo que tambien seria O(n^2) porque tendrían que recorerse todos los caminos posibles para poder determinar cual es la mayor cantidad de dias que pueden tardar en podrirse todas las naranjas.

es correcto mi razonamiento?

Yojan Antonio Pardo Zabala

student•

Aqui dejo mi solucion en java.

Que tal les parece, se me hizo parecido al de los movimientos del caballo

public class RottingOranges {

    private static final Set<Point> VISITED_ROTTEN_ORANGES = new LinkedHashSet<>();

    private static final Set<Point> SPREAD_DIRECTIONS = Set.of(
            new Point(1,0),
            new Point(0,1),
            new Point(-1,0),
            new Point(0,-1)
    );
    public static void main(String[] args) {
        final int[][] orangesBox = buildOrangesBox();
        System.out.println("here is the oranges box: ");
        printMatrix(orangesBox);
        System.out.printf("Days required for oranges to be rotten: [%d]", calculateDays(orangesBox));
    }

    /**
     * returns the quantity of days required to the adjacent healthy oranges to rotten ones to be rotten
     * a healthy orange gets rotten when past a day besides to a rotten orange
     *
     * @param orangesBox with the oranges distribution
     * @return the quantity of days required for oranges to get rotten
     */
    private static int calculateDays(int[][] orangesBox) {
        if(Objects.isNull(orangesBox) || orangesBox.length == 0){
            return 0;
        }

        int days = 0;

        for(int x = 0; x < orangesBox.length; x++){
            for(int y = 0; y < orangesBox[x].length; y++){
                if(orangesBox[x][y] == 2){
                    final Point rottenOrange = new Point(x,y);
                    VISITED_ROTTEN_ORANGES.add(rottenOrange);
                    days = Math.max(days, startSpreading(rottenOrange, orangesBox));
                }
            }
        }


        return days;
    }

    private static int startSpreading(Point point, int[][] orangesBox) {
        int days = 0;

        final Queue<Point> adjacentOranges = getAdjacentOranges(point, orangesBox);

        while (!adjacentOranges.isEmpty()){

            int size = adjacentOranges.size();

            for(int i = 0; i < size; i++){
                Point healthyOrange = adjacentOranges.poll();
                orangesBox[healthyOrange.getX()][healthyOrange.getY()] = 2;
                adjacentOranges.addAll(getAdjacentOranges(healthyOrange, orangesBox));
            }

            printMatrix(orangesBox);

            days ++;
        }

        return days;
    }

    private static Queue<Point> getAdjacentOranges(Point point, int[][] orangesBox) {
        final Queue<Point> adjacentOranges = new LinkedList<>();

        for(Point direction : SPREAD_DIRECTIONS){
            Point newDirection = new Point(point.getX() + direction.getX(), point.getY() + direction.getY());

            if(newDirection.getX() >= 0
                    && newDirection.getY() >= 0
                    && newDirection.getX() < orangesBox.length
                    && newDirection.getY() < orangesBox[newDirection.getX()].length
                    && !VISITED_ROTTEN_ORANGES.contains(newDirection)
                    && orangesBox[newDirection.getX()][newDirection.getY()] == 1
            ) {
                VISITED_ROTTEN_ORANGES.add(newDirection);
                adjacentOranges.add(newDirection);
            }
        }

        return adjacentOranges;
    }

    /**
     * this method builds an oranges box
     * 0 is an empty space in the box
     * 1 is a healthy orange
     * 2 is a rotten orange
     * @return an n*m matrix with oranges
     */
    private static int[][] buildOrangesBox() {
        return new int[][] {
                {1,1,1,0},
                {1,0,1,1},
                {1,2,0,0},
                {1,1,0,1},
        };
    }
}