Pasos mínimos para convertir todas las rutas de arriba a la izquierda a abajo a la derecha en Matrix como palíndromo | conjunto 2

Dada una array mat[][] con N filas y M columnas. La tarea es encontrar el número mínimo de cambios requeridos en la array de modo que cada camino desde la parte superior izquierda hasta la parte inferior derecha sea un camino palindrómico. En un camino, solo se permiten movimientos hacia la derecha y hacia abajo de una celda a otra celda.

Ejemplos: 

Entrada: mat[][] = {{1, 2}, {3, 1}}
Salida: 0
Explicación:
Cada camino en la array de arriba a la izquierda a abajo a la derecha es palindrómico.
Rutas => {1, 2, 1}, {1, 3, 1}

Entrada: mat[][] = {{1, 2}, {3, 5}}
Salida: 1
Explicación:
Solo se requiere un cambio para que cada ruta sea palindrómica.
Eso es => mat[1][1] = 1
Caminos => {1, 2, 1}, {1, 3, 1}

Enfoque ingenuo: para el enfoque ingenuo, consulte esta publicación.

Enfoque Eficiente: La idea es descartar el uso de un espacio extra que es el uso de HashMap . Siga los pasos que se indican a continuación:

1. La distancia posible desde la parte superior izquierda y la parte inferior derecha están en el rango de 0 a N + M – 2 . Por lo tanto, cree una array 2D de dimensiones [N + M – 1][10] .
2. Almacene la frecuencia de las distancias en una array mientras considera el número de fila (en el rango de 0 a N + M – 2) como distancia y el número de columna (0 a 9) como un elemento en la array dada.
3. Para que el número de cambios sea mínimo , cambie cada celda en la distancia X con un valor que tenga la frecuencia más alta entre todos los valores en la distancia X.
4. El número mínimo de pasos necesarios es la suma de la diferencia de los valores totales de frecuencia y el valor máximo de frecuencia para cada distancia.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define N 7
 
// Function for counting minimum
// number of changes
int countChanges(int matrix[][N],
                 int n, int m)
{
    // Distance of elements from (0, 0)
    // will is i range [0, n + m - 2]
    int dist = n + m - 1;
 
    // Store frequencies of [0, 9]
    // at distance i
    int freq[dist][10];
 
    // Initialize frequencies as 0
    for (int i = 0; i < dist; i++) {
        for (int j = 0; j < 10; j++)
            freq[i][j] = 0;
    }
 
    // Count frequencies of [0, 9]
    for (int i = 0; i < n; i++) {
 
        for (int j = 0; j < m; j++) {
 
            // Increment frequency of
            // value matrix[i][j]
            // at distance i+j
            freq[i + j][matrix[i][j]]++;
        }
    }
 
    int min_changes_sum = 0;
    for (int i = 0; i < dist / 2; i++) {
 
        int maximum = 0;
        int total_values = 0;
 
        // Find value with max frequency
        // and count total cells at distance i
        // from front end and rear end
        for (int j = 0; j < 10; j++) {
 
            maximum = max(maximum, freq[i][j]
                    + freq[n + m - 2 - i][j]);
 
            total_values += (freq[i][j]
                   + freq[n + m - 2 - i][j]);
        }
 
        // Change all values to the
        // value with max frequency
        min_changes_sum += (total_values
                            - maximum);
    }
 
    // Return the answer
    return min_changes_sum;
}
 
// Driver Code
int main()
{
    // Given Matrix
    int mat[][N] = { { 1, 2 }, { 3, 5 } };
 
    // Function Call
    cout << countChanges(mat, 2, 2);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
     
static final int N = 7;
 
// Function for counting minimum
// number of changes
static int countChanges(int matrix[][],
                        int n, int m)
{
     
    // Distance of elements from (0, 0)
    // will is i range [0, n + m - 2]
    int dist = n + m - 1;
 
    // Store frequencies of [0, 9]
    // at distance i
    int [][]freq = new int[dist][10];
 
    // Initialize frequencies as 0
    for(int i = 0; i < dist; i++)
    {
        for(int j = 0; j < 10; j++)
            freq[i][j] = 0;
    }
 
    // Count frequencies of [0, 9]
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
             
            // Increment frequency of
            // value matrix[i][j]
            // at distance i+j
            freq[i + j][matrix[i][j]]++;
        }
    }
 
    int min_changes_sum = 0;
    for(int i = 0; i < dist / 2; i++)
    {
        int maximum = 0;
        int total_values = 0;
 
        // Find value with max frequency
        // and count total cells at distance i
        // from front end and rear end
        for(int j = 0; j < 10; j++)
        {
            maximum = Math.max(maximum, freq[i][j] +
                            freq[n + m - 2 - i][j]);
 
            total_values += (freq[i][j] +
                             freq[n + m - 2 - i][j]);
        }
         
        // Change all values to the
        // value with max frequency
        min_changes_sum += (total_values -
                            maximum);
    }
 
    // Return the answer
    return min_changes_sum;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given matrix
    int mat[][] = { { 1, 2 }, { 3, 5 } };
 
    // Function call
    System.out.print(countChanges(mat, 2, 2));
}
}
 
// This code is contributed by Rohit_ranjan

# Python3 program for the above approach
 
# Function for counting minimum
# number of changes
def countChanges(matrix, n, m):
 
    # Distance of elements from (0, 0)
    # will is i range [0, n + m - 2]
    dist = n + m - 1
 
    # Store frequencies of [0, 9]
    # at distance i
    # Initialize all with zero
    freq = [[0] * 10 for i in range(dist)]
 
    # Count frequencies of [0, 9]
    for i in range(n):
        for j in range(m):
 
            # Increment frequency of
            # value matrix[i][j]
            # at distance i+j
            freq[i + j][matrix[i][j]] += 1
 
    min_changes_sum = 0
 
    for i in range(dist // 2):
        maximum = 0
        total_values = 0
 
        # Find value with max frequency
        # and count total cells at distance i
        # from front end and rear end        
        for j in range(10):
            maximum = max(maximum, freq[i][j] +
                       freq[n + m - 2 - i][j])
 
            total_values += (freq[i][j] +
                 freq[n + m - 2 - i][j])
 
        # Change all values to the value
        # with max frequency
        min_changes_sum += (total_values -
                            maximum)
                             
    # Return the answer
    return min_changes_sum
 
# Driver code
if __name__ == '__main__':
 
    # Given matrix
    mat = [ [ 1, 2 ], [ 3, 5 ] ]
 
    # Function call
    print(countChanges(mat, 2, 2))
 
# This code is contributed by himanshu77

// C# program for the above approach
using System;
 
class GFG{
     
//static readonly int N = 7;
 
// Function for counting minimum
// number of changes
static int countChanges(int [,]matrix,
                        int n, int m)
{
     
    // Distance of elements from (0, 0)
    // will is i range [0, n + m - 2]
    int dist = n + m - 1;
 
    // Store frequencies of [0, 9]
    // at distance i
    int [,]freq = new int[dist, 10];
 
    // Initialize frequencies as 0
    for(int i = 0; i < dist; i++)
    {
        for(int j = 0; j < 10; j++)
            freq[i, j] = 0;
    }
 
    // Count frequencies of [0, 9]
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
             
            // Increment frequency of
            // value matrix[i,j]
            // at distance i+j
            freq[i + j, matrix[i, j]]++;
        }
    }
 
    int min_changes_sum = 0;
    for(int i = 0; i < dist / 2; i++)
    {
        int maximum = 0;
        int total_values = 0;
 
        // Find value with max frequency
        // and count total cells at distance i
        // from front end and rear end
        for(int j = 0; j < 10; j++)
        {
            maximum = Math.Max(maximum, freq[i, j] +
                            freq[n + m - 2 - i, j]);
 
            total_values += (freq[i, j] +
                             freq[n + m - 2 - i, j]);
        }
         
        // Change all values to the
        // value with max frequency
        min_changes_sum += (total_values -
                            maximum);
    }
 
    // Return the answer
    return min_changes_sum;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given matrix
    int [,]mat = { { 1, 2 }, { 3, 5 } };
 
    // Function call
    Console.Write(countChanges(mat, 2, 2));
}
}
 
// This code is contributed by Rohit_ranjan

<script>
 
// JavaScript program for the above approach
var N = 7;
 
// Function for counting minimum
// number of changes
function countChanges(matrix, n, m)
{
    // Distance of elements from (0, 0)
    // will is i range [0, n + m - 2]
    var dist = n + m - 1;
 
    // Store frequencies of [0, 9]
    // at distance i
    var freq = Array.from(Array(dist), ()=>Array(10));
 
    // Initialize frequencies as 0
    for (var i = 0; i < dist; i++) {
        for (var j = 0; j < 10; j++)
            freq[i][j] = 0;
    }
 
    // Count frequencies of [0, 9]
    for (var i = 0; i < n; i++) {
 
        for (var j = 0; j < m; j++) {
 
            // Increment frequency of
            // value matrix[i][j]
            // at distance i+j
            freq[i + j][matrix[i][j]]++;
        }
    }
 
    var min_changes_sum = 0;
    for (var i = 0; i < parseInt(dist / 2); i++) {
 
        var maximum = 0;
        var total_values = 0;
 
        // Find value with max frequency
        // and count total cells at distance i
        // from front end and rear end
        for (var j = 0; j < 10; j++) {
 
            maximum = Math.max(maximum, freq[i][j]
                    + freq[n + m - 2 - i][j]);
 
            total_values += (freq[i][j]
                   + freq[n + m - 2 - i][j]);
        }
 
        // Change all values to the
        // value with max frequency
        min_changes_sum += (total_values
                            - maximum);
    }
 
    // Return the answer
    return min_changes_sum;
}
 
// Driver Code
 
// Given Matrix
var mat = [[1, 2], [3, 5 ]];
 
// Function Call
document.write( countChanges(mat, 2, 2));
 
 
</script>

1

Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)