Dada una array mat][][] de tamaño M x N que representa el mapa topográfico de una región, y 0 denota tierra y 1 denota elevación, la tarea es maximizar la altura en la array asignando a cada celda un valor no negativo. altura tal que la altura de una celda terrestre es 0 y dos celdas adyacentes deben tener una diferencia de altura absoluta de 1 como máximo.
Ejemplos:
Entrada: mat[][] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}} Salida: {{0, 1,
2 }, {1, 0, 1 }, {2, 1, 0}}Entrada: mat[][] = {{0, 0, 1}, {1, 0, 0}, {0, 0, 0}} Salida: {{1, 1, 0}, {0, 1
, 1 }, {1, 2, 2}}
Enfoque: La idea es utilizar BFS . Siga los pasos a continuación para resolver el problema:
- Inicialice una array 2d , altura de tamaño M x N para almacenar la array de salida final.
- Inicialice una cola de pair , queue<pair<int, int>>q para almacenar los índices de pares para BFS .
- Atraviese la array y marque la altura de la celda terrestre como 0 y póngalas en cola, también márquelas como visitadas.
- Realizar BFS :
- Quite una celda de la cola y verifique todas sus 4 celdas adyacentes, si alguna de ellas aún no ha sido visitada, marque la altura de esta celda como 1 + la altura de la celda actual.
- Marque todas las celdas adyacentes no visitadas como visitadas.
- Repita esto a menos que la cola se quede vacía.
- Imprima la array de altura final.
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;
#define M 3
#define N 3
// Utility function to find the matrix
// having the maximum height
void findHeightMatrixUtil(int mat[][N],
int height[M][N])
{
// Stores index pairs for bfs
queue<pair<int, int> > q;
// Stores info about the visited cells
int vis[M][N] = { 0 };
// Traverse the matrix
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (mat[i][j] == 1) {
q.push({ i, j });
height[i][j] = 0;
vis[i][j] = 1;
}
}
}
// Breadth First Search
while (q.empty() == 0) {
pair<int, int> k = q.front();
q.pop();
// x & y are the row & column
// of current cell
int x = k.first, y = k.second;
// Check all the 4 adjacent cells
// and marking them as visited
// if not visited yet also marking
// their height as 1 + height of cell (x, y)
if (x > 0 && vis[x - 1][y] == 0) {
height[x - 1][y] = height[x][y] + 1;
vis[x - 1][y] = 1;
q.push({ x - 1, y });
}
if (y > 0 && vis[x][y - 1] == 0) {
height[x][y - 1] = height[x][y] + 1;
vis[x][y - 1] = 1;
q.push({ x, y - 1 });
}
if (x < M - 1 && vis[x + 1][y] == 0) {
height[x + 1][y] = height[x][y] + 1;
vis[x + 1][y] = 1;
q.push({ x + 1, y });
}
if (y < N - 1 && vis[x][y + 1] == 0) {
height[x][y + 1] = height[x][y] + 1;
vis[x][y + 1] = 1;
q.push({ x, y + 1 });
}
}
}
// Function to find the matrix having
// the maximum height
void findHeightMatrix(int mat[][N])
{
// Stores output matrix
int height[M][N];
// Calling the helper function
findHeightMatrixUtil(mat, height);
// Print the final output matrix
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++)
cout << height[i][j] << " ";
cout << endl;
}
}
// Driver Code
int main()
{
// Given matrix
int mat[][N]
= { { 0, 0 }, { 0, 1 } };
// Function call to find
// the matrix having
// the maximum height
findHeightMatrix(mat);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static final int M = 3;
static final int N = 3;
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Utility function to find the matrix
// having the maximum height
static void findHeightMatrixUtil(int mat[][],
int height[][])
{
// Stores index pairs for bfs
Queue<pair > q = new LinkedList<>();
// Stores info about the visited cells
int [][]vis = new int[M][N];
// Traverse the matrix
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (mat[i][j] == 1) {
q.add(new pair( i, j ));
height[i][j] = 0;
vis[i][j] = 1;
}
}
}
// Breadth First Search
while (q.isEmpty() == false) {
pair k = q.peek();
q.remove();
// x & y are the row & column
// of current cell
int x = k.first, y = k.second;
// Check all the 4 adjacent cells
// and marking them as visited
// if not visited yet also marking
// their height as 1 + height of cell (x, y)
if (x > 0 && vis[x - 1][y] == 0) {
height[x - 1][y] = height[x][y] + 1;
vis[x - 1][y] = 1;
q.add(new pair( x - 1, y ));
}
if (y > 0 && vis[x][y - 1] == 0) {
height[x][y - 1] = height[x][y] + 1;
vis[x][y - 1] = 1;
q.add(new pair( x, y - 1 ));
}
if (x < M - 1 && vis[x + 1][y] == 0) {
height[x + 1][y] = height[x][y] + 1;
vis[x + 1][y] = 1;
q.add(new pair( x + 1, y ));
}
if (y < N - 1 && vis[x][y + 1] == 0) {
height[x][y + 1] = height[x][y] + 1;
vis[x][y + 1] = 1;
q.add(new pair( x, y + 1 ));
}
}
}
// Function to find the matrix having
// the maximum height
static void findHeightMatrix(int mat[][])
{
// Stores output matrix
int [][]height = new int[M][N];
// Calling the helper function
findHeightMatrixUtil(mat, height);
// Print the final output matrix
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++)
System.out.print(height[i][j]+ " ");
System.out.println();
}
}
// Driver Code
public static void main(String[] args)
{
// Given matrix
int mat[][]
= { { 0, 0,0 }, { 0, 1,0 },{ 0, 0,0 } };
// Function call to find
// the matrix having
// the maximum height
findHeightMatrix(mat);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach M = 3 N = 3 # Utility function to find the matrix # having the maximum height def findHeightMatrixUtil(mat, height): # Stores index pairs for bfs q = [] # Stores info about the visited cells vis = [[0 for i in range(N)]for j in range(M)] # Traverse the matrix for i in range(M): for j in range(N): if (mat[i][j] == 1): q.append([i, j]) height[i][j] = 0 vis[i][j] = 1 # Breadth First Search while (len(q) != 0): k = q[0] q = q[1:] # x & y are the row & column # of current cell x,y = k[0],k[1] # Check all the 4 adjacent cells # and marking them as visited # if not visited yet also marking # their height as 1 + height of cell (x, y) if (x > 0 and vis[x - 1][y] == 0): height[x - 1][y] = height[x][y] + 1 vis[x - 1][y] = 1 q.append([x - 1, y]) if (y > 0 and vis[x][y - 1] == 0): height[x][y - 1] = height[x][y] + 1 vis[x][y - 1] = 1 q.append([x, y - 1]) if (x < M - 1 and vis[x + 1][y] == 0): height[x + 1][y] = height[x][y] + 1 vis[x + 1][y] = 1 q.append([x + 1, y]) if (y < N - 1 and vis[x][y + 1] == 0): height[x][y + 1] = height[x][y] + 1 vis[x][y + 1] = 1 q.append([x, y + 1]) return height # Function to find the matrix having # the maximum height def findHeightMatrix(mat): # Stores output matrix height = [[0 for i in range(N)]for j in range(M)] # Calling the helper function height = findHeightMatrixUtil(mat, height) # Print the final output matrix for i in range(M): for j in range(N): print(height[i][j] ,end = " ") print() # Driver Code # Given matrix mat = [ [ 0, 0,0], [0, 1,0 ],[0, 0,0 ]] # Function call to find # the matrix having # the maximum height findHeightMatrix(mat) # This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
static readonly int M = 3;
static readonly int N = 3;
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Utility function to find the matrix
// having the maximum height
static void findHeightMatrixUtil(int [,]mat,
int [,]height)
{
// Stores index pairs for bfs
Queue<pair > q = new Queue<pair>();
// Stores info about the visited cells
int [,]vis = new int[M,N];
// Traverse the matrix
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (mat[i,j] == 1) {
q.Enqueue(new pair( i, j ));
height[i,j] = 0;
vis[i,j] = 1;
}
}
}
// Breadth First Search
while (q.Count != 0 )
{
pair k = q.Peek();
q.Dequeue();
// x & y are the row & column
// of current cell
int x = k.first, y = k.second;
// Check all the 4 adjacent cells
// and marking them as visited
// if not visited yet also marking
// their height as 1 + height of cell (x, y)
if (x > 0 && vis[x - 1, y] == 0) {
height[x - 1, y] = height[x, y] + 1;
vis[x - 1, y] = 1;
q.Enqueue(new pair( x - 1, y ));
}
if (y > 0 && vis[x, y - 1] == 0) {
height[x, y - 1] = height[x, y] + 1;
vis[x, y - 1] = 1;
q.Enqueue(new pair( x, y - 1 ));
}
if (x < M - 1 && vis[x + 1, y] == 0) {
height[x + 1, y] = height[x, y] + 1;
vis[x + 1, y] = 1;
q.Enqueue(new pair( x + 1, y ));
}
if (y < N - 1 && vis[x, y + 1] == 0) {
height[x, y + 1] = height[x, y] + 1;
vis[x, y + 1] = 1;
q.Enqueue(new pair( x, y + 1 ));
}
}
}
// Function to find the matrix having
// the maximum height
static void findHeightMatrix(int [,]mat)
{
// Stores output matrix
int [,]height = new int[M, N];
// Calling the helper function
findHeightMatrixUtil(mat, height);
// Print the readonly output matrix
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++)
Console.Write(height[i,j]+ " ");
Console.WriteLine();
}
}
// Driver Code
public static void Main(String[] args)
{
// Given matrix
int [,]mat
= { { 0, 0,0 }, { 0, 1,0 },{ 0, 0,0 } };
// Function call to find
// the matrix having
// the maximum height
findHeightMatrix(mat);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
var M = 3;
var N = 3;
// Utility function to find the matrix
// having the maximum height
function findHeightMatrixUtil(mat, height)
{
// Stores index pairs for bfs
var q = [];
// Stores info about the visited cells
var vis = Array.from(Array(M), ()=>Array(N).fill(0));
// Traverse the matrix
for (var i = 0; i < M; i++) {
for (var j = 0; j < N; j++) {
if (mat[i][j] == 1) {
q.push([i, j]);
height[i][j] = 0;
vis[i][j] = 1;
}
}
}
// Breadth First Search
while (q.length != 0) {
var k = q[0];
q.shift();
// x & y are the row & column
// of current cell
var x = k[0], y = k[1];
// Check all the 4 adjacent cells
// and marking them as visited
// if not visited yet also marking
// their height as 1 + height of cell (x, y)
if (x > 0 && vis[x - 1][y] == 0) {
height[x - 1][y] = height[x][y] + 1;
vis[x - 1][y] = 1;
q.push([x - 1, y]);
}
if (y > 0 && vis[x][y - 1] == 0) {
height[x][y - 1] = height[x][y] + 1;
vis[x][y - 1] = 1;
q.push([x, y - 1]);
}
if (x < M - 1 && vis[x + 1][y] == 0) {
height[x + 1][y] = height[x][y] + 1;
vis[x + 1][y] = 1;
q.push([x + 1, y]);
}
if (y < N - 1 && vis[x][y + 1] == 0) {
height[x][y + 1] = height[x][y] + 1;
vis[x][y + 1] = 1;
q.push([x, y + 1]);
}
}
return height;
}
// Function to find the matrix having
// the maximum height
function findHeightMatrix(mat)
{
// Stores output matrix
var height = Array.from(Array(M), ()=>Array(N).fill(0));
// Calling the helper function
height = findHeightMatrixUtil(mat, height);
// Print the final output matrix
for (var i = 0; i < M; i++) {
for (var j = 0; j < N; j++)
document.write( height[i][j] + " ");
document.write("<br>");
}
}
// Driver Code
// Given matrix
var mat = [ [ 0, 0,0], [0, 1,0 ],[0, 0,0 ]];
// Function call to find
// the matrix having
// the maximum height
findHeightMatrix(mat);
</script>
Producción:
2 1 2 1 0 1 2 1 2
Complejidad de Tiempo: O(M * N)
Espacio Auxiliar: O(M * N)
Publicación traducida automáticamente
Artículo escrito por sumukh_bhardwaj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA