Introducción

1

Grafos y Árboles: Estructuras de Datos Avanzadas

2

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

3

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

4

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

5

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

6

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

7

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

8

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

9

Recorridos y Profundidad en Árboles Binarios y Enearios

10

Suma de Caminos en Árboles Binarios

11

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

12

Playground: Sum Root to Leaf Numbers

13

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

14

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

15

Conteo de Islas en Matrices con DFS

16

Playground: Number of Islands

17

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

18

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

19

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

BFS

20

Algoritmo BFS: Recorrido en Anchura de Grafos y Árboles

21

Implementación de BFS en Árboles usando Python

22

Movimiento mínimo de caballo en ajedrez infinito

23

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

24

Playground: Minimum Knights Moves

25

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

26

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

27

Resolución de Rotting Oranges usando BFS

28

Playground: Rotting Oranges

29

Propagación de Plagas en Matrices usando BFS en Java

30

Construcción de Puentes Cortos entre Islas en Matrices Binarias

31

Resolución del Problema Shortest Bridge con DFS y BFS

32

Playground: Shortest Bridge Between Islands

33

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

34

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

35

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

Backtrack

36

Algoritmo Backtracking: Solución de Problemas Complejos

37

Combinaciones de Letras en Números Telefónicos

38

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

39

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

40

Playground: Letter Combinations of a Phone Number

41

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

42

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

43

Playground: Restore IP Addresses

44

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

45

Búsqueda de Palabras en Matrices usando Backtracking y DFS

46

Playgrund: Word Search

47

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

48

Resolución del problema de las n reinas en ajedrez

49

Ejercicios de Backtracking: Combinaciones y Permutaciones

50

Combinaciones y Permutaciones con Backtracking

Próximos pasos

51

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

52

Algoritmos y Estructuras de Datos en la Ingeniería

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Propagación de Plagas en Matrices usando BFS en Java

29/52
Recursos

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

Aportes 2

Preguntas 1

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

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;
}

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