Solución de Rotting Oranges

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.

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 ```c# #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() { 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"; }

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