Introducci贸n

1

驴Qu茅 es un grafo?

2

驴Qu茅 es un 谩rbol?

3

驴Qu茅 es recursi贸n?

4

Aplicaciones reales de grafos y 谩rboles

5

Formas de representar un grafo

DFS

6

An谩lisis de DFS: algoritmo de b煤squeda en profundidad

7

Programando DFS de forma recursiva

8

Otras formas de programar DFS

9

Recorridos y profundidad de un 脕rbol

10

Sum Root to Leaf Numbers: an谩lisis del problema

11

Soluci贸n de Sum Root to Leaf Numbers

12

Playground: Sum Root to Leaf Numbers

13

Programando Sum Root to Leaf Numbers en Golang

14

Number of Islands: an谩lisis del problema

15

Soluci贸n de Number of Islands

16

Playground: Number of Islands

17

Programando Number of Islands en Python

18

Ejercicios recomendados de DFS

19

Ejercicios resueltos de DFS

BFS

20

An谩lisis de BFS: algoritmo de b煤squeda en anchura

21

Programando BFS con Python

22

Minimum Knights Moves (movimientos de caballo en ajedrez): an谩lisis del problema

23

Soluci贸n de Minimum Knights Moves

24

Playground: Minimum Knights Moves

25

Programando Minimum Knights Moves con Python

26

Rotting Oranges: an谩lisis del problema

27

Soluci贸n de Rotting Oranges

28

Playground: Rotting Oranges

29

Rotting Oranges con Java

30

Shortest Bridge Between Islands: an谩lisis del problema

31

Soluci贸n de Shortest Bridge Between Islands

32

Playground: Shortest Bridge Between Islands

33

Programando Shortest Bridge Between Islands con Python

34

Ejercicios recomendados de BFS

35

Ejercicios resueltos de BFS

Backtrack

36

Algoritmo de Backtrack

37

Letter Combinations of a Phone Number: an谩lisis del problema

38

Soluci贸n de Letter Combinations of a Phone Number

39

Programando Letter Combinations of a Phone Number con C++

40

Playground: Letter Combinations of a Phone Number

41

Restore IP Addresses: an谩lisis del problema

42

Programando Restore IP Addresses con C++

43

Playground: Restore IP Addresses

44

Word Search: an谩lisis del problema

45

Soluci贸n de Word Search

46

Playgrund: Word Search

47

Programando Word Search JavaScript

48

Reto: N Queens Puzzle

49

Ejercicios recomendados de Backtrack

50

Ejercicios resueltos de Backtrack

Pr贸ximos pasos

51

驴Qu茅 otros algoritmos y tipos de grafos puedes aprender?

52

驴Quieres m谩s cursos avanzados de algoritmos?

No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Soluci贸n de Rotting Oranges

27/52
Recursos

Aportes 3

Preguntas 0

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

Se me ocurre como soluci贸n al problema, analizar a partir de 鈥渞adios鈥 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.

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?
Aqui dejo mi solucion en java. Que tal les parece, se me hizo parecido al de los movimientos del caballo ```java 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}, }; } } ```