Bárbara obtuvo muy buenas calificaciones en la escuela el año pasado, por lo que sus padres decidieron regalarle un conejo como mascota. Estaba tan emocionada que construyó una casa para el conejo, que se puede ver como una cuadrícula 2D con filas RR y columnas CC.
A los conejos les encanta saltar, así que Bárbara apiló varias cajas en varias celdas de la cuadrícula. Cada cuadro es un cubo con dimensiones iguales, que coinciden exactamente con las dimensiones de una celda de la cuadrícula.
Sin embargo, Bárbara pronto se da cuenta de que puede ser peligroso para el conejo hacer saltos de más de 11 cajas de altura, por lo que decide evitarlo haciendo algunos ajustes en la casa. Para cada par de celdas adyacentes, a Bárbara le gustaría que su diferencia absoluta en altura sea como máximo 11 cajas. Dos celdas se consideran adyacentes si comparten un lado común.
Como todas las cajas están pegadas con pegamento, Bárbara no puede quitar las cajas que están allí inicialmente, sin embargo, puede agregar cajas encima de ellas. Puede agregar tantos cuadros como quiera, a tantas celdas como quiera (que pueden ser cero). Ayúdala a determinar cuál es el número mínimo total de cajas que se deben agregar para que la casa del conejo esté segura.
O
Dada una array de R filas y M columnas. Haga que la diferencia absoluta entre las celdas adyacentes sea menor o igual a 1 aumentando solo el valor de la celda. El incremento total realizado en las celdas debe minimizarse. La tarea es devolver las operaciones de incremento mínimo realizadas.
Ejemplo:
Entrada: [[0 0 0],
[0 2 0],
[0 0 0]]
Salida: 4
Explicación: la celda en el medio de la cuadrícula tiene una diferencia absoluta en la altura de 2, la altura de las cuatro celdas adyacentes celdas se incrementa exactamente en 1 unidad para que la diferencia absoluta entre
cualquier par de celdas adyacentes sea como máximo 1. La array resultante será:
[[0 1 0],
[1 2 1],
[0 1 0]]Entrada: [[1 0 5 4 2],
[1 5 6 4 8],
[2 3 4 2 1],
[2 3 4 9 8]]
Salida: 52
Explicación: La array resultante será: [[3 4 5 6 7],
[4 5 6 7 8 ],
[5 6 7 8 7],
[6 7 8 9 8]]
Enfoque: Dado el problema se puede resolver usando el algoritmo de Dijkstra de fuentes múltiples . El enfoque es almacenar las celdas con los valores más grandes en una cola de prioridad , sacar la cola de prioridad una por una y actualizar las celdas adyacentes en consecuencia, mientras actualizamos el valor de la celda, también actualizaremos nuestra cola de prioridad.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
void solve(long long int r, long long int c,
vector<vector<long long int> >& grid)
{
priority_queue<pair<long long int,
pair<long long int, long long int> > >
pq;
for (long long int i = 0; i < r; i++) {
for (long long int j = 0; j < c; j++) {
pq.push(make_pair(grid[i][j],
make_pair(i, j)));
}
}
long long int res = 0;
while (!pq.empty()) {
long long int height = pq.top().first,
i = pq.top().second.first,
j = pq.top().second.second;
pq.pop();
if (height != grid[i][j])
continue;
if (i == 0) {
// Down
if (i != r - 1) {
if (grid[i + 1][j] < height - 1) {
res += height - 1 - grid[i + 1][j];
grid[i + 1][j] = height - 1;
pq.push(make_pair(height - 1,
make_pair(i + 1, j)));
}
}
// Left
if (j != 0) {
if (grid[i][j - 1] < height - 1) {
res += height - 1 - grid[i][j - 1];
grid[i][j - 1] = height - 1;
pq.push(make_pair(height - 1,
make_pair(i, j - 1)));
}
}
// Right
if (j != c - 1) {
if (grid[i][j + 1] < height - 1) {
res += height - 1 - grid[i][j + 1];
grid[i][j + 1] = height - 1;
pq.push(make_pair(height - 1,
make_pair(i, j + 1)));
}
}
}
else if (i == r - 1) {
// Up
if (i != 0) {
if (grid[i - 1][j] < height - 1) {
res += height - 1 - grid[i - 1][j];
grid[i - 1][j] = height - 1;
pq.push(make_pair(height - 1,
make_pair(i - 1, j)));
}
}
// Left
if (j != 0) {
if (grid[i][j - 1] < height - 1) {
res += height - 1 - grid[i][j - 1];
grid[i][j - 1] = height - 1;
pq.push(make_pair(height - 1,
make_pair(i, j - 1)));
}
}
// Right
if (j != c - 1) {
if (grid[i][j + 1] < height - 1) {
res += height - 1 - grid[i][j + 1];
grid[i][j + 1] = height - 1;
pq.push(make_pair(height - 1,
make_pair(i, j + 1)));
}
}
}
else {
// Down
if (grid[i + 1][j] < height - 1) {
res += height - 1 - grid[i + 1][j];
grid[i + 1][j] = height - 1;
pq.push(make_pair(height - 1,
make_pair(i + 1, j)));
}
// Up
if (grid[i - 1][j] < height - 1) {
res += height - 1 - grid[i - 1][j];
grid[i - 1][j] = height - 1;
pq.push(make_pair(height - 1,
make_pair(i - 1, j)));
}
// Left
if (j != 0) {
if (grid[i][j - 1] < height - 1) {
res += height - 1 - grid[i][j - 1];
grid[i][j - 1] = height - 1;
pq.push(make_pair(height - 1,
make_pair(i, j - 1)));
}
}
// Right
if (j != c - 1) {
if (grid[i][j + 1] < height - 1) {
res += height - 1 - grid[i][j + 1];
grid[i][j + 1] = height - 1;
pq.push(make_pair(height - 1,
make_pair(i, j + 1)));
}
}
}
}
cout << res;
}
// Driver code
int main()
{
long long int r = 4, c = 5;
vector<vector<long long int> > grid{ { 1, 0, 5, 4, 2 },
{ 1, 5, 6, 4, 8 },
{ 2, 3, 4, 2, 1 },
{ 2, 3, 4, 9, 8 } };
solve(r, c, grid);
}
52
Complejidad de tiempo: O(RM * Log(RM))
Espacio auxiliar: O(RM)
Publicación traducida automáticamente
Artículo escrito por satyamkant2805 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA