Playground: Rotting Oranges

Clase 28 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles

Contenido del curso

Introducción

DFS

BFS

Backtrack

Próximos pasos

Tomar examen

Comentarios

Diego Portillo

student•

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

John Eduard Meneses González

student•

My Solution!!

José Ramón García

student•

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

José Ramón García

student•

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

Carlos Hernandez

student•

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

Miguel Angel Reyes Moreno

student•

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;

}

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

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        

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

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

Playground: Rotting Oranges

Introducción

Grafos y Árboles: Estructuras de Datos Avanzadas

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

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

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

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

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

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

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

Recorridos y Profundidad en Árboles Binarios y Enearios

Suma de Caminos en Árboles Binarios

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

Playground: Sum Root to Leaf Numbers

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

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

Conteo de Islas en Matrices con DFS

Playground: Number of Islands

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

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

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

BFS

Algoritmo BFS: Recorrido en Anchura de Grafos y Árboles

Implementación de BFS en Árboles usando Python

Movimiento mínimo de caballo en ajedrez infinito

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

Playground: Minimum Knights Moves

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

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

Resolución de Rotting Oranges usando BFS