Propagación de Plagas en Matrices usando BFS en Java

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

Resumen

¿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:

Inicialización de la cola: Comienza agregando todas las posiciones que contienen plantas ya podridas. Estas se identifican con el valor 2.
Direcciones posibles: Las direcciones definidas permiten expandirse a los vecinos (arriba, abajo, izquierda, derecha).
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!

John Eduard Meneses González

student•

My Solution!!

Tomás Santa Cruz

student•

Solucion en c++

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_set>

using namespace std;

vector<pair<int, int>> foundRottingOranges(vector<vector<int>> &grid)
{
    vector<pair<int, int>> rottenOranges;
    for (int i = 0; i < grid.size(); i++)
    {
        for (int j = 0; j < grid[i].size(); j++)
        {
            if (grid[i][j] == 2)
            {
                rottenOranges.push_back({i, j});
            }
        }
    }
    return rottenOranges;
}

int rottingOranges(vector<vector<int>> &grid)
{
    vector<pair<int, int>> origins = foundRottingOranges(grid);

    if (origins.empty()) // No hay naranjas podridas
    {
        return -1;
    }
    queue<pair<int, int>> q;
    for (const auto &origin : origins)
    {
        q.push(origin);
    }

    unordered_set<int> visited;

    int days = 0;
    for (const auto &origin : origins)
    {
        visited.emplace(origin.first * grid[0].size() + origin.second);
    }

    while (!q.empty())
    {
        int size = q.size();
        for (int i = 0; i < size; i++)
        {
            pair<int, int> current = q.front();
            q.pop();

            int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            for (const auto &dir : directions)
            {
                int newRow = current.first + dir[0];
                int newCol = current.second + dir[1];
                int newPosition = newRow * grid[0].size() + newCol;

                if (newRow >= 0 && newRow < grid.size() && newCol >= 0 && newCol < grid[0].size() &&
                    grid[newRow][newCol] == 1 && visited.find(newPosition) == visited.end())
                {
                    q.push({newRow, newCol});
                    grid[newRow][newCol] = 2;
                    visited.insert(newPosition);
                }
            }
        }
        if (!q.empty())
        {
            days++;
        }
    }

    for (const auto &row : grid)
    {
        for (int cell : row)
        {
            if (cell == 1)
            {
                return -1;
            }
        }
    }

    return days;
}

int main()
{
    vector<vector<int>> grid{{2, 1, 1}
                            ,{1, 1, 0},
                             {0, 1, 2}};
    cout << rottingOranges(grid) << endl;
    return 0;
}

Manuel Juarez

student•

import collections
import random


def bfs(
    apple_field: list[list[int]]
):
    rotten_queue = collections.deque()
    for i in range(len(apple_field[0])):
        for j in range(len(apple_field)):
            if apple_field[i][j] == 2:
                rotten_queue.append((i, j, 0))
    max_time = 0
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    while rotten_queue:
        x, y, time = rotten_queue.popleft()
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if (0 <= nx < len(apple_field)) & (0 <= ny < len(apple_field[0])):
                if apple_field[nx][ny] == 1:
                    apple_field[nx][ny] = 2
                    new_time = time+1
                    max_time = max(max_time, new_time)
                    rotten_queue.append((nx, ny, new_time))

    return apple_field, max_time


def generate_field(rows, cols):
    # Generate a random 2D array (apple field) with values 0, 1, 2
    apple_field = [[random.choice([0, 1])
                   for _ in range(rows)] for _ in range(cols)]

   # Assisgns only a few rotten apples into  the field
    for _ in range(3):
        x = random.randint(0, len(apple_field)-1)
        y = random.randint(0, len(apple_field)-1)
        apple_field[x][y] = 2
    print("Initial apple field:")
    for row in apple_field:
        print(row)

    return apple_field


def main():

    rows, cols = 5, 5  # You can change the size as needed
    apple_field = generate_field(rows, cols)
    result_field, max_time = bfs(apple_field)

    print("\nApple field after propagation:")
    for row in apple_field:
        print(row)
    print(f"\nMax days for propagation: {max_time}")

    total_rotten_apples = sum(
        [1 if result_field[i][j] == 2 else 0 for i in range(rows) for j in range(cols)])
    total_healthy_apples = sum(
        [1 if result_field[i][j] == 1 else 0 for i in range(rows) for j in range(cols)])
    print(f"Total rotten apples: {total_rotten_apples}")
    print(f"Total healthy apples: {total_healthy_apples}")


if __name__ == '__main__':
    main()

Edwin Uldarico Hernandez Osorio

student•

Cuantos estados posibles hay? fresca = 1 podrida = 2 vacía ? = Null ??

Si hay espacios vacíos no creo que el código sea correcto usar cultivo[x][y] != 2 pues tecnicamente infecta posiciones que ni tienen fruta ? estoy mal ?

ahora imagino que lo primero que podemos hacer es verificar si hay islas, regiones que no puedan infectar otras, y si hay mas de una saber que una infección nunca llegara al 100% del cultivo

Daniel Ortiz

student•

Algo que inclui, es un catch cuando buscas en un extremo, ya que en este caso te sales del array y una bandera para que sume por una vez en la cola


from queue import Queue

STEPS = [(0, 1), (0, -1), (1, 0), (-1, 0)]


def rotting_oranges(farm: list[list[int]]) -> int:
    if farm is None or len(farm) == 0:
        return 0
    bad_tomatoes = Queue()
    good_tomatoes = 0
    for i in range(len(farm)):
        for j in range(len(farm[0])):
            if farm[i][j] == 2:
                bad_tomatoes.put((i, j))
            if farm[i][j] == 1:
                good_tomatoes += 1
    if good_tomatoes == 0:
        return 0
    days = 1
    while not bad_tomatoes.empty():
        should_sum = False

        position = bad_tomatoes.get()
        for step in STEPS:
            next_position = (position[0] + step[0], position[1] + step[1])
            try:
                if farm[next_position[0]][next_position[1]] == 1:
                    should_sum = True
                    farm[next_position[0]][next_position[1]] = 2
                    good_tomatoes -= 1
                    bad_tomatoes.put(next_position)
            except IndexError:
                continue
        if should_sum:
            days += 1
    return -1 if good_tomatoes != 0 else days


if __name__ == '__main__':
    assert rotting_oranges([[2, 1, 1], [1, 1, 0], [0, 1, 1]]) == 4
    assert rotting_oranges([[1, 1, 1], [1, 1, 0], [0, 1, 1]]) == -1
    assert rotting_oranges([[0, 1, 1], [1, 1, 0], [0, 1, 2]]) == 5

Propagación de Plagas en Matrices usando BFS en Java

Introducción

Grafos y Árboles: Estructuras de Datos Avanzadas

Estructuras de Datos: Introducción a Árboles y Sus Propiedades

Recursión: Concepto y Aplicaciones Prácticas con Ejemplos

Aplicaciones Prácticas de Grafos en Tecnología e Industria

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

Búsqueda en Profundidad (DFS) en Árboles y Grafos

Implementación de DFS recursivo para búsqueda en árboles

Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo

Recorridos y Profundidad en Árboles Binarios y Enearios

Suma de Caminos en Árboles Binarios

Suma de Números de Raíz a Hoja en Árboles

Playground: Sum Root to Leaf Numbers

Implementación de Algoritmo DFS en Árboles Binarios con Golang

Resolución del Problema de Número de Islas con DFS

Conteo de Islas en Matrices con DFS

Playground: Number of Islands

Implementación de "Número de Islas" con Recursión en Python

Ejercicios Prácticos de Búsqueda en Profundidad (DFS)

Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes

BFS

Algoritmo BFS: Recorrido en Anchura de Grafos y Árboles

Implementación de BFS en Árboles usando Python

Movimiento mínimo de caballo en ajedrez infinito

Resolviendo el Problema Mínimo de Movimiento del Caballo en Ajedrez

Playground: Minimum Knights Moves

Resolución de Problemas de Caballos de Ajedrez con BFS en Python

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

Resolución de Rotting Oranges usando BFS

Playground: Rotting Oranges

Propagación de Plagas en Matrices usando BFS en Java

Construcción de Puentes Cortos entre Islas en Matrices Binarias

Resolución del Problema Shortest Bridge con DFS y BFS

Playground: Shortest Bridge Between Islands

Búsqueda del camino más corto entre islas usando BFS en Python

Búsqueda en anchura: Ejercicios prácticos y aplicaciones

Ejercicios avanzados de búsqueda en anchura (BFS) en programación

Backtrack

Algoritmo Backtracking: Solución de Problemas Complejos

Combinaciones de Letras en Números Telefónicos

Combinaciones de Letras a partir de un Número de Teléfono

Generación de combinaciones de letras con teclados numéricos en C++

Playground: Letter Combinations of a Phone Number

Generación de Direcciones IP Válidas a partir de Cadenas Numéricas

Generación de IPs válidas con backtracking en C++

Playground: Restore IP Addresses

Búsqueda de Palabras en Matrices: Solución y Complejidad

Búsqueda de Palabras en Matrices usando Backtracking y DFS

Playgrund: Word Search

Implementación de búsqueda de palabras en matrices con DFS en JavaScript

Resolución del problema de las n reinas en ajedrez

Ejercicios de Backtracking: Combinaciones y Permutaciones

Combinaciones y Permutaciones con Backtracking

Próximos pasos

Algoritmos de Grafos: MIN/MAX-HIP, TRI, Topological Sort y Dijkstra

Algoritmos y Estructuras de Datos en la Ingeniería