Número mínimo de ladrillos que se pueden cruzar

Dada una array 2D arr[][] , que representa el ancho de los ladrillos de la misma altura presentes en una pared, la tarea es encontrar la cantidad mínima de ladrillos que se pueden intersectar dibujando una línea recta desde la parte superior hasta la parte inferior de la pared. 
Nota: Se dice que una línea interseca un ladrillo si lo atraviesa y no se interseca si toca el límite de un ladrillo.

Ejemplos:

Entrada: array[][] ={{1, 2, 2, 1}, {3, 1, 2}, {1, 3, 2}, {2, 4}, {3, 1, 2}, { 1, 3, 1, 1}}

Salida: 2
Explicación: Considerando la esquina superior izquierda de la array 2D como origen, la línea se dibuja en la coordenada x = 4 en el eje x, de modo que cruza los ladrillos en el 1er y 4to nivel, resultando en el número mínimo de ladrillos cruzados.

Entrada: arr[][] = {{1, 1, 1}}
Salida: 0
Explicación: La línea se puede dibujar en la coordenada x = 1 o x = 2 en el eje x de modo que no cruce ningún ladrillo resultante en el mínimo número de ladrillos cruzados.

Enfoque ingenuo: el enfoque más simple es considerar líneas rectas que se pueden dibujar en cada coordenada posible en el eje x , a lo largo del ancho de la pared, considerando x = 0 en la esquina superior izquierda de la pared. Luego, calcule el número de ladrillos insertados en cada caso e imprima el recuento mínimo obtenido. 

Tiempo Complejidad: O(N * M) donde N es el número total de ladrillos y M es el ancho total del muro
Espacio Auxiliar: O(1) 

Enfoque: para optimizar el enfoque anterior, la idea es almacenar la cantidad de ladrillos que terminan en un cierto ancho en el eje x en un hashmap y luego encontrar la línea donde termina la mayor cantidad de ladrillos. Después de obtener este conteo, réstelo de la altura total de la pared para obtener el número mínimo de ladrillos cruzados. 

Siga los pasos a continuación para resolver el problema:

  • Inicialice un mapa hash , M para almacenar la cantidad de ladrillos que terminan en un cierto ancho en el eje x.
  • Atraviese la array , arr usando la variable i para almacenar el índice de fila
    • Inicialice una variable, ancho como 0 para almacenar la posición final.
    • Almacene el tamaño de la fila actual en una variable X .
    • Iterar en el rango [0, X-2] usando la variable j
      • Incremente el valor de ancho en arr[i][j] e incremente el valor de ancho en M en 1 .
      • Además, realice un seguimiento de la mayor cantidad de ladrillos que terminan en un cierto ancho y guárdelo en una variable, res .
  • Reste el valor de res de la altura total del muro y guárdelo en una variable, ans .
  • Imprime el valor de ans como resultado.

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;
 
// Function to find a line across a wall such
// that it intersects minimum number of bricks
void leastBricks(vector<vector<int> > wall)
{
    // Declare a hashmap
    unordered_map<int, int> map;
 
    // Store the maximum number of
    // brick ending a point on x-axis
    int res = 0;
 
    // Iterate over all the rows
    for (vector<int> list : wall) {
 
        // Initialize width as 0
        int width = 0;
 
        // Iterate over individual bricks
        for (int i = 0; i < list.size() - 1; i++) {
 
            // Add the width of the current
            // brick to the total width
            width += list[i];
 
            // Increment number of bricks
            // ending at this width position
            map[width]++;
 
            // Update the variable, res
            res = max(res, map[width]);
        }
    }
 
    // Print the answer
    cout << wall.size() - res;
}
 
// Driver Code
int main()
{
    // Given Input
    vector<vector<int> > arr{
        { 1, 2, 2, 1 }, { 3, 1, 2 },
        { 1, 3, 2 }, { 2, 4 },
        { 3, 1, 2 }, { 1, 3, 1, 1 }
    };
 
    // Function Call
    leastBricks(arr);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
 
public class GFG
{
 
    // Function to find a line across a wall such
    // that it intersects minimum number of bricks
    static void leastBricks(ArrayList<ArrayList<Integer> > wall)
    {
       
        // Declare a hashmap
        HashMap<Integer, Integer> map = new HashMap<>();
 
        // Store the maximum number of
        // brick ending a point on x-axis
        int res = 0;
 
        // Iterate over all the rows
        for (ArrayList<Integer> list : wall) {
 
            // Initialize width as 0
            int width = 0;
 
            // Iterate over individual bricks
            for (int i = 0; i < list.size() - 1; i++) {
 
                // Add the width of the current
                // brick to the total width
                width += list.get(i);
 
                // Increment number of bricks
                // ending at this width position
                map.put(width,
                        map.getOrDefault(width, 0) + 1);
 
                // Update the variable, res
                res = Math.max(res,
                               map.getOrDefault(width, 0));
            }
        }
 
        // Print the answer
        System.out.println(wall.size() - res);
    }
 
    // Driver code
    public static void main(String[] args)
    {
      // Given Input
        ArrayList<ArrayList<Integer> > arr
            = new ArrayList<>();
        arr.add(new ArrayList<>(Arrays.asList(1, 2, 2, 1)));
        arr.add(new ArrayList<>(Arrays.asList(3, 1, 2)));
        arr.add(new ArrayList<>(Arrays.asList(1, 3, 2)));
        arr.add(new ArrayList<>(Arrays.asList(2, 4)));
        arr.add(new ArrayList<>(Arrays.asList(3, 1, 2)));
        arr.add(new ArrayList<>(Arrays.asList(1, 3, 1, 1)));
 
        // Function Call
        leastBricks(arr);
    }
}
 
// This code is contributed by abhinavjain194

Python3

# Python 3 program for the above approach
from collections import defaultdict
 
# Function to find a line across a wall such
# that it intersects minimum number of bricks
def leastBricks(wall):
 
    # Declare a hashmap
    map = defaultdict(int)
 
    # Store the maximum number of
    # brick ending a point on x-axis
    res = 0
 
    # Iterate over all the rows
    for list in wall:
 
        # Initialize width as 0
        width = 0
 
        # Iterate over individual bricks
        for i in range(len(list) - 1):
 
            # Add the width of the current
            # brick to the total width
            width += list[i]
 
            # Increment number of bricks
            # ending at this width position
            map[width] += 1
 
            # Update the variable, res
            res = max(res, map[width])
 
    # Print the answer
    print(len(wall) - res)
 
 
# Driver Code
if __name__ == "__main__":
 
    # Given Input
    arr = [
        [1, 2, 2, 1], [3, 1, 2],
        [1, 3, 2], [2, 4],
        [3, 1, 2], [1, 3, 1, 1]
    ]
 
    # Function Call
    leastBricks(arr)
 
    # This code is contributed by ukasp.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
  
// Function to find a line across a wall such
// that it intersects minimum number of bricks
static void leastBricks(List<List<int>> wall)
{
     
    // Declare a hashmap
    Dictionary<int,
               int> map = new Dictionary<int,
                                         int>();
 
    // Store the maximum number of
    // brick ending a point on x-axis
    int res = 0;
 
    // Iterate over all the rows
    foreach (List<int> subList in wall)
    {
         
        // Initialize width as 0
        int width = 0;
        for(int i = 0; i < subList.Count - 1; i++)
        {
             
            // Add the width of the current
            // brick to the total width
            width += subList[i];
             
            // Increment number of bricks
            // ending at this width position
            if (map.ContainsKey(width))
                map[width]++;
            else
                map.Add(width, 1);
             
            // Update the variable, res
            res = Math.Max(res, map[width]);
        }
    }
 
    // Print the answer
    Console.Write(wall.Count-res);
}
 
// Driver Code
public static void Main()
{
     
    // Given Input
    List<List<int>> myList = new List<List<int>>();
    myList.Add(new List<int>{ 1, 2, 2, 1 });
    myList.Add(new List<int>{ 3, 1, 2 });
    myList.Add(new List<int>{ 1, 3, 2 });
    myList.Add(new List<int>{ 2, 4 });
    myList.Add(new List<int>{ 3, 1, 2 });
    myList.Add(new List<int>{ 1, 3, 1, 1 });
     
    // Function Call
    leastBricks(myList);
}
}
 
// This code is contributed by bgangwar59

Javascript

<script>
 
// JavaScript program for the above approach
 
 
// Function to find a line across a wall such
// that it intersects minimum number of bricks
function leastBricks(wall) {
    // Declare a hashmap
    let map = new Map();
 
    // Store the maximum number of
    // brick ending a point on x-axis
    let res = 0;
 
    // Iterate over all the rows
    for (let list of wall) {
 
        // Initialize width as 0
        let width = 0;
 
        // Iterate over individual bricks
        for (let i = 0; i < list.length - 1; i++) {
 
            // Add the width of the current
            // brick to the total width
            width += list[i];
 
            // Increment number of bricks
            // ending at this width position
            if (map.has(width)) {
                map.set(width, map.get(width) + 1);
            } else {
                map.set(width, 1)
            }
 
            // Update the variable, res
            res = Math.max(res, map.get(width));
        }
    }
 
    // Print the answer
    document.write(wall.length - res);
}
 
// Driver Code
 
// Given Input
let arr = [
    [1, 2, 2, 1], [3, 1, 2],
    [1, 3, 2], [2, 4],
    [3, 1, 2], [1, 3, 1, 1]
];
 
// Function Call
leastBricks(arr);
 
</script>
Producción: 

2

 

Tiempo de Complejidad: O(N) donde N es el número total de ladrillos en la pared
Espacio Auxiliar: O(M) donde M es el ancho total de la pared

Publicación traducida automáticamente

Artículo escrito por rajgaur98 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 *