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