Altura máxima de una elevación posible de modo que las celdas de array adyacentes tengan una diferencia de altura máxima de 1

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *