|Agua atrapada en matriz 2DDifícil
Ejercicio00:00

¿Quieres un reto mayor?

Resuelve en 15:00

info

Importante: Para que se registre el resultado tienes que iniciar sesión.

Agua atrapada en matriz 2D

Difícil50 pts·Algoritmos

Enunciado

Agua atrapada en matriz 2D

Dada una matriz 2D de enteros heights donde heights[i][j] representa la altura del terreno en la celda (i, j), calcula el volumen total de agua de lluvia que puede quedar atrapada.

El agua puede fluir hacia cualquiera de las 4 celdas adyacentes (arriba, abajo, izquierda, derecha) y se desbordará por los bordes de la matriz.

Algoritmo sugerido

Usa BFS con una cola de prioridad (min-heap) iniciando desde todos los bordes:

  1. Inserta todas las celdas del borde en el heap con su altura.
  2. Extrae la celda de menor altura. Para cada vecino no visitado:
    • El nivel de agua en el vecino = max(altura_del_vecino, nivel_actual)
    • Si nivel_actual > altura_del_vecino, el vecino retiene nivel_actual - altura_del_vecino unidades.
  3. Repite hasta vaciar el heap.

Ejemplo

const heights = [
  [1, 4, 3],
  [3, 0, 3],
  [2, 3, 1]
];
trapRainWater2D(heights); // 3
// La celda central tiene altura 0.
// El camino mínimo de escape tiene nivel 3 → retiene 3 unidades.

Restricciones

  • 1 <= m, n <= 200 donde m × n es el tamaño de la matriz
  • 0 <= heights[i][j] <= 20000
  • Si la matriz tiene menos de 3 filas o menos de 3 columnas, no puede retener agua → retorna 0
Restriccionesexpand_more
  • Dificultad: Difícil
  • Completa todos los test cases para obtener los 50 puntos.
  • No modificar la línea export al final del archivo.
  • Se recomienda evitar el uso de inteligencia artificial para que realmente tú practiques los ejercicios.

Puedes usar console.log() para depurar. Los resultados aparecen en la Consola de salida, no en el navegador.

Inicia sesión para reaccionar
Inicia sesión para reaccionar
Agua atrapada en matriz 2D — Difícil | Coding Challenges · Coding Challenges