Dada una array arr[][] de dimensión M*N que consta de números enteros positivos, donde arr[i][j] representa la altura de cada celda unitaria, la tarea es encontrar el volumen total de agua atrapada en la array después de la lluvia .
Ejemplos:
Entrada: arr[][] = {{4, 2, 7}, {2, 1, 10}, {5, 10, 2}}
Salida: 1
Explicación:
El agua de lluvia se puede atrapar de la siguiente manera:
- Las celdas, {(0, 0), (0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1), (2, 2 )} atrapa 0 unidad de volumen de agua de lluvia ya que toda el agua sale de la array ya que las celdas están en el límite.
- La celda (2, 2) atrapa 1 unidad de volumen de agua de lluvia entre las celdas {(0, 1), (1, 0), (1, 2) y (2, 1)}.
Por lo tanto, un total de 1 unidad de volumen de agua de lluvia ha quedado atrapada dentro de la array.
Entrada: arr[][] = {{1, 4, 3, 1, 3, 2}, {3, 2, 1, 3, 2, 4}, {2, 3, 3, 2, 3, 1} }
Salida: 4
Enfoque: El problema dado se puede resolver usando la técnica Greedy y Min-Heap . Siga los pasos a continuación para resolver el problema:
- Inicialice un Min-Heap usando la cola de prioridad , digamos PQ , para almacenar los pares de posiciones de una celda y su altura.
- Empuje todas las celdas de límite en el PQ y marque todas las celdas empujadas como visitadas.
- Inicialice dos variables, digamos ans como 0 y maxHeight como 0 para almacenar el volumen total y la altura máxima de todas las celdas en PQ respectivamente.
- Iterar hasta que PQ no esté vacío y realizar los siguientes pasos:
- Almacene el Node superior de PQ en una variable, digamos front , y borre el elemento superior de PQ .
- Actualice el valor de maxHeight como el máximo de maxHeight y front.height .
- Ahora, recorra todos los Nodes adyacentes de la celda actual (front.X, front.Y) y haga lo siguiente:
- Si la celda adyacente es válida, es decir, la celda no está fuera de los límites y aún no se ha visitado, entonces, inserte el valor de la celda adyacente en PQ.
- Si la altura de la celda adyacente es menor que maxHeight , entonces incremente la ans por la diferencia de maxHeight y la altura de la celda adyacente.
- Finalmente, después de completar los pasos anteriores, imprima el valor de ans como el agua resultante atrapada después de la lluvia.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the direction of all the
// adjacent cells
vector<vector<int> > dir
= { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
// Node structure
struct node {
int height;
int x, y;
};
// Comparator function to implement
// the min heap using priority queue
struct Compare {
// Comparator function
bool operator()(node const& a, node const& b)
{
return a.height > b.height;
}
};
// Function to find the amount of water
// the matrix is capable to hold
int trapRainWater(vector<vector<int> >& heightMap)
{
int M = heightMap.size();
int N = heightMap[0].size();
// Stores if a cell of the matrix
// is visited or not
vector<vector<bool> > visited(M,
vector<bool>(N, false));
// Initialize a priority queue
priority_queue<node, vector<node>, Compare> pq;
// Traverse over the matrix
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
// If element is not on
// the boundary
if (!(i == 0 || j == 0 || i == M - 1
|| j == N - 1))
continue;
// Mark the current cell
// as visited
visited[i][j] = true;
// Node for priority queue
node t;
t.x = i;
t.y = j;
t.height = heightMap[i][j];
// Pushe all the adjacent
// node in the pq
pq.push(t);
}
}
// Stores the total volume
int ans = 0;
// Stores the maximum height
int max_height = INT_MIN;
// Iterate while pq is not empty
while (!pq.empty()) {
// Store the top node of pq
node front = pq.top();
// Delete the top element of pq
pq.pop();
// Update the max_height
max_height = max(max_height, front.height);
// Stores the position of the
// current cell
int curr_x = front.x;
int curr_y = front.y;
for (int i = 0; i < 4; i++) {
int new_x = curr_x + dir[i][0];
int new_y = curr_y + dir[i][1];
// If adjacent cells are out
// of bound or already visited
if (new_x < 0 || new_y < 0 || new_x >= M
|| new_y >= N || visited[new_x][new_y]) {
continue;
}
// Stores the height of the
// adjacent cell
int height = heightMap[new_x][new_y];
// If height of current cell
// is smaller than max_height
if (height < max_height) {
// Increment the ans by
// (max_height-height)
ans = ans + (max_height - height);
}
// Define a new node
node temp;
temp.x = new_x;
temp.y = new_y;
temp.height = height;
// Push the current node
// in the pq
pq.push(temp);
// Mark the current cell
// as visited
visited[new_x][new_y] = true;
}
}
return ans;
}
// Driver Code
int main()
{
vector<vector<int> > arr = { { 1, 4, 3, 1, 3, 2 },
{ 3, 2, 1, 3, 2, 4 },
{ 2, 3, 3, 2, 3, 1 } };
cout << trapRainWater(arr);
return 0;
}
Producción
4
Complejidad de Tiempo: (N * M * log(N * M))
Espacio Auxiliar: O(N * M)
Publicación traducida automáticamente
Artículo escrito por surajanand y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA