Clase 28 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles
Contenido del curso
Diego Portillo
John Eduard Meneses González
José Ramón García
José Ramón García
Carlos Hernandez
Miguel Angel Reyes Moreno
export function orangesRotting(cultivo) { let queue = []; let visited = new Set(); let days = []; const rows = cultivo.length; const columns = cultivo[0].length; for (let i = 0; i < rows; i++) { for (let j = 0; i < columns; i++) { if (cultivo[i][j] == 2) { queue.push([`${i},${j}`, 0]) } } } while (queue.length > 0) { const [coordinates, step] = queue.shift() const [x, y] = coordinates.split(',').map(Number) if (!visited.has(coordinates)) { visited.add(coordinates); const right = [x + 1, y] const left = [x - 1, y] const up = [x, y + 1] const down = [x, y - 1] if (-1 < right[0] && right[0] < rows && [1].includes(cultivo[right[0]][right[1]])) { cultivo[right[0]][right[1]] = 2 queue.push([`${right[0]},${right[1]}`, step + 1]) } if (-1 < left[0] && left[0] < rows && [1].includes(cultivo[left[0]][left[1]])) { cultivo[left[0]][left[1]] = 2 queue.push([`${left[0]},${left[1]}`, step + 1]) } if (-1 < up[0] && up[0] < columns && [1].includes(cultivo[up[0]][up[1]])) { cultivo[up[0]][up[1]] = 2 queue.push([`${up[0]},${up[1]}`, step + 1]) } if (-1 < down[0] && down[0] < columns && [1].includes(cultivo[down[0]][down[1]])) { cultivo[down[0]][down[1]] = 2 queue.push([`${down[0]},${down[1]}`, step + 1]) } } days.push(step) } for (let i = 0; i < rows; i++) { for (let j = 0; j < columns; j++) { if (cultivo[i][j] == 1) { return -1; } } } console.log(cultivo) const maxDays = Math.max(...days); console.log(maxDays) return maxDays; }
My Solution!!
Solución en Python
from collections import deque def counting_days_left(crop): total_oranges = 0 total_rotten_oranges = 0 rotten_oranges = deque([]) n = len(crop) m = len(crop[0]) visited = set() days = -1 def searching_oranges(x,y,i,j): nonlocal total_rotten_oranges if (x+i,y+j) not in visited and (0<=x+i<n and 0<=y+j<m) and crop[x+i][y+j] == 1: visited.add((x+i,y+j)) crop[x+i][y+j] = 2 total_rotten_oranges += 1 rotten_oranges.append((x+i,y+j)) for i in range(n): for j in range(m): value = crop[i][j] if value == 1: total_oranges += 1 if value == 2: rotten_oranges.append((i,j)) while rotten_oranges: for _ in range(len(rotten_oranges)): x,y = rotten_oranges.popleft() searching_oranges(x,y,1,0) # rigth searching_oranges(x,y,-1,0) # left searching_oranges(x,y,0,1) # above searching_oranges(x,y,0,-1) # behind days += 1 if total_oranges - total_rotten_oranges == 0: return days else: return -1
Solución en Java
export function orangesRotting(cultivo) { const totalOranges = { value: 0 }; const totalRottenOranges = { value: 0 }; const rottenOranges = []; const visited = new Set(); let days = -1; const n = cultivo.length; const m = cultivo[0].length; function searchingOranges(x, y, i, j) { const ni = x + i; const nj = y + j; const key = `${ni},${nj}`; if ( ni >= 0 && ni < n && nj >= 0 && nj < m && cultivo[ni][nj] === 1 && !visited.has(key) ) { visited.add(key); cultivo[ni][nj] = 2; totalRottenOranges.value++; rottenOranges.push([ni, nj]); } } // Inicializamos conteos for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { const value = cultivo[i][j]; if (value === 1) totalOranges.value++; if (value === 2) rottenOranges.push([i, j]); } } while (rottenOranges.length > 0) { const size = rottenOranges.length; for (let i = 0; i < size; i++) { const [x, y] = rottenOranges.shift(); searchingOranges(x, y, 1, 0); // abajo searchingOranges(x, y, -1, 0); // arriba searchingOranges(x, y, 0, 1); // derecha searchingOranges(x, y, 0, -1); // izquierda } days++; } if (totalOranges.value - totalRottenOranges.value === 0) { return days; } else { return -1; } }
Código Javascript:
const canOrangeBeInfected = (crop, i, j) => { return (crop[i - 1]?.[j] === 1) || (crop[i][j + 1] === 1) || (crop[i + 1]?.[j] === 1) || (crop[i][j - 1] === 1) } const infectContagiousSpots = (crop, i, j, queue) => { if (crop[i - 1]?.[j] === 1) { queue.push({ i: i - 1, j }); crop[i - 1][j] = 2; } if (crop[i]?.[j + 1] === 1) { queue.push({ i, j: j + 1 }); crop[i][j + 1] = 2; } if (crop[i + 1]?.[j] === 1) { queue.push({ i: i + 1, j }); crop[i + 1][j] = 2; } if (crop[i]?.[j - 1] === 1) { queue.push({ i, j: j - 1 }); crop[i][j - 1] = 2; } } export function orangesRotting(crop) { let rottenOrangesQueue = []; for (let i = 0; i < crop.length; i++) { const row = crop[i]; for (let j = 0; j < row.length; j++) { const spot = row[j]; if (spot === 1 && !canOrangeBeInfected(crop, i, j)) return -1; if (spot === 2) { rottenOrangesQueue.push({ i, j }); } } } let days = -1; while (rottenOrangesQueue.length > 0) { console.log(crop) let counter = rottenOrangesQueue.length - 1; while (counter >= 0) { const current = rottenOrangesQueue.shift(); const { i, j } = current; infectContagiousSpots(crop, i, j, rottenOrangesQueue); counter--; } days++; } return days; }
código en javascript:
class Solution {
orangesRotting(grid) {
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const rottenOranges = [];
let freshOranges = 0;
let minutesPassed = 0;
// Count fresh oranges and add rotten oranges to the queue
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === 1) {
freshOranges++;
}
if (grid[i][j] === 2) {
rottenOranges.push([i, j]);
}
}
}
if (freshOranges === 0) {
return 0; // No fresh oranges to rot
}
// BFS process to rot adjacent fresh oranges
while (rottenOranges.length > 0) {
const size = rottenOranges.length;
let newRotting = false;
for (let i = 0; i < size; i++) {
const [x, y] = rottenOranges.shift();
for (const [dx, dy] of directions) {
const nx = x + dx;
const ny = y + dy;
if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && grid[nx][ny] === 1) {
grid[nx][ny] = 2;
freshOranges--;
rottenOranges.push([nx, ny]);
newRotting = true;
}
}
}
if (newRotting) {
minutesPassed++;
}
}
return freshOranges > 0 ? -1 : minutesPassed;
}
}
