Incrementos mínimos requeridos para hacer palindrómica la array dada

Dada una array M[][] de dimensiones N * M , la tarea es encontrar el número mínimo de incrementos de elementos de la array en 1 necesarios para convertir la array en una array palindrómica.

Una array palíndromo es una array en la que cada fila y columna es un palíndromo . 
 

Ejemplo:

Entrada: N = 4, M = 2, arr[][]={{5, 3}, {3, 5}, {5, 3}, {3, 5}}
Salida: 8
Explicación: La array palindrómica ser arr[][] = {{5, 5}, {5, 5}, {5, 5}, {5, 5}}

Entrada: N = 3, M = 3, arr[][]={{1, 2, 1}, {3, 4, 1}, {1, 2, 1}}
Salida: 2
Explicación:
La array palindrómica ser arr[][] = {{1, 2, 1}, {3, 4, 3}, {1, 2, 1}}

Enfoque: si el valor de arr[0][0] es igual a X, entonces los valores de arr[M-1][0] , arr[0][M-1] y arr[N-1][M- 1] también debe ser igual a X por la propiedad del palíndromo. Una propiedad similar es válida para todos los elementos arr[i][j], arr[N – i – 1][j], arr[N – i – 1][M – j – 1], arr[i][M – j – 1] también. Por lo tanto, el problema se reduce a encontrar el número que se puede obtener de los cuadruplicados en cuestión con incrementos mínimos. Siga los pasos a continuación para resolver el problema:

1. Divide la array en 4 cuadrantes. Recorrer la array desde (0, 0) índice hasta (((N + 1) / 2)-1, ((M + 1) / 2)-1) (Solo en el primer cuadrante).
2. Para cada índice (i, j) almacene ( i, j), (N – i – 1, j), (N – i – 1, M – j – 1), (i, M – j – 1) índices en un conjunto para que solo los índices únicos estén presentes en el conjunto.
3. Luego almacene los elementos presentes en esos índices únicos en valores vectoriales y evalúe el máximo en este vector.
4. Ahora agregue la diferencia entre el valor máximo y el resto de los elementos del vector de valores y actualice el ans.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to evaluate minimum number
// of operation required to convert
// the matrix to a palindrome matrix
int palindromeMatrix(int N, int M, vector<vector<int> > arr)
{
    // Variable to store number
    // of operations required
    int ans = 0;
 
    // Iterate over the first
    // quadrant of the matrix
    for (int i = 0; i < (N + 1) / 2; i++) {
 
        for (int j = 0; j < (M + 1) / 2; j++) {
 
            // Store positions of all four
            // values from four quadrants
            set<pair<int, int> > s;
            s.insert({ i, j });
            s.insert({ i, M - j - 1 });
            s.insert({ N - i - 1, j });
            s.insert({ N - i - 1, M - j - 1 });
 
            // Store the values having
            // unique indexes
            vector<int> values;
            for (pair<int, int> p : s) {
 
                values.push_back(
                    arr[p.first][p.second]);
            }
 
            // Largest value in the values vector
            int max = *max_element(
                values.begin(),
                values.end());
 
            // Evaluate minimum increments
            // required to make all vector
            // elements equal
            for (int k = 0; k < values.size(); k++) {
 
                ans += max - values[k];
            }
        }
    }
 
    // Print the answer
    cout << ans;
}
 
// Driver Code
int main()
{
    int N = 3, M = 3;
    vector<vector<int> > arr
        = { { 1, 2, 1 },
            { 3, 4, 1 },
            { 1, 2, 1 } };
 
    // Function Call
    palindromeMatrix(N, M, arr);
 
    return 0;
}

// Java program for the
// above approach
import java.util.*;
class GFG{
 
static class pair
{
  int first, second;
  public pair(int first,
              int second) 
  {
    this.first = first;
    this.second = second;
  }   
}
   
// Function to evaluate minimum number
// of operation required to convert
// the matrix to a palindrome matrix
static void palindromeMatrix(int N, int M,
                             int[][] arr)
{
  // Variable to store number
  // of operations required
  int ans = 0;
 
  // Iterate over the first
  // quadrant of the matrix
  for (int i = 0;
           i < (N + 1) / 2; i++)
  {
    for (int j = 0;
             j < (M + 1) / 2; j++)
    {
      // Store positions of all four
      // values from four quadrants
      HashSet<pair> s =
              new HashSet<>();
      s.add(new pair(i, j));
      s.add(new pair(i, M - j - 1));
      s.add(new pair(N - i - 1, j));
      s.add(new pair(N - i - 1,
                     M - j - 1));
 
      // Store the values having
      // unique indexes
      Vector<Integer> values =
             new Vector<>();
      for (pair p : s)
      {
        values.add(
        arr[p.first][p.second]);
      }
 
      // Largest value in the
      // values vector
      int max =
          Collections.max(values);
 
      // Evaluate minimum increments
      // required to make all vector
      // elements equal
      for (int k = 1;
               k < values.size(); k++)
      {
        ans += max - values.get(k);
      }
    }
  }
   
  // Print the answer
  System.out.print(ans);
}
 
// Driver Code
public static void main(String[] args)
{
  int N = 3, M = 3;
  int[][] arr = {{1, 2, 1},
                 {3, 4, 1},
                 {1, 2, 1}};
 
  // Function Call
  palindromeMatrix(N, M, arr);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for the above approach
 
# Function to evaluate minimum number
# of operation required to convert
# the matrix to a palindrome matrix
def palindromeMatrix(N, M, arr):
     
    # Variable to store number
    # of operations required
    ans = 0
 
    # Iterate over the first
    # quadrant of the matrix
    for i in range((N + 1) // 2):
        for j in range((M + 1) // 2):
             
            # Store positions of all four
            # values from four quadrants
            s = {}
            s[(i, j)] = 1
            s[(i, M - j - 1)] = 1
            s[(N - i - 1, j)] = 1
            s[(N - i - 1, M - j - 1)] = 1
 
            # Store the values having
            # unique indexes
            values = []
             
            for p, q in s:
                values.append(arr[p][q])
 
            # Largest value in the values vector
            maxm = max(values)
 
            # Evaluate minimum increments
            # required to make all vector
            # elements equal
            for k in range(len(values)):
                ans += maxm - values[k]
 
    # Print the answer
    print(ans)
 
# Driver Code
if __name__ == '__main__':
     
    N, M = 3, 3
     
    arr = [ [ 1, 2, 1 ],
            [ 3, 4, 1 ],
            [ 1, 2, 1 ] ]
 
    # Function Call
    palindromeMatrix(N, M, arr)
 
# This code is contributed by mohit kumar 29

// C# program for the
// above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
public class pair
{
  public int first, second;
  public pair(int first,
              int second) 
  {
    this.first = first;
    this.second = second;
  }   
}
   
// Function to evaluate minimum number
// of operation required to convert
// the matrix to a palindrome matrix
static void palindromeMatrix(int N, int M,
                             int[,] arr)
{
   
  // Variable to store number
  // of operations required
  int ans = 0;
 
  // Iterate over the first
  // quadrant of the matrix
  for(int i = 0;
          i < (N + 1) / 2; i++)
  {
    for(int j = 0;
            j < (M + 1) / 2; j++)
    {
       
      // Store positions of all four
      // values from four quadrants
      HashSet<pair> s = new HashSet<pair>();
      s.Add(new pair(i, j));
      s.Add(new pair(i, M - j - 1));
      s.Add(new pair(N - i - 1, j));
      s.Add(new pair(N - i - 1,
                     M - j - 1));
       
      // Store the values having
      // unique indexes
      List<int> values = new List<int>();
       
      foreach (pair p in s)
      {
        values.Add(arr[p.first, p.second]);
      }
 
      // Largest value in the
      // values vector
      values.Sort();
      int max = values[values.Count - 1];
       
      // Evaluate minimum increments
      // required to make all vector
      // elements equal
      for(int k = 1;
              k < values.Count; k++)
      {
        ans += max - values[k];
      }
    }
  }
   
  // Print the answer
  Console.Write(ans);
}
 
// Driver Code
public static void Main(String[] args)
{
  int N = 3, M = 3;
  int[,] arr = { { 1, 2, 1 },
                 { 3, 4, 1 },
                 { 1, 2, 1 } };
 
  // Function Call
  palindromeMatrix(N, M, arr);
}
}
 
// This code is contributed by Amit Katiyar

<script>
// Javascript program for the
// above approach
 
class pair
{
    constructor(first, second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to evaluate minimum number
// of operation required to convert
// the matrix to a palindrome matrix
function palindromeMatrix(N, M, arr)
{
 
    // Variable to store number
  // of operations required
  let ans = 0;
  
  // Iterate over the first
  // quadrant of the matrix
  for (let i = 0;
           i < Math.floor((N + 1) / 2); i++)
  {
    for (let j = 0;
             j < Math.floor((M + 1) / 2); j++)
    {
     
      // Store positions of all four
      // values from four quadrants
      let s = new Set();
      s.add(new pair(i, j));
      s.add(new pair(i, M - j - 1));
      s.add(new pair(N - i - 1, j));
      s.add(new pair(N - i - 1,
                     M - j - 1));
  
      // Store the values having
      // unique indexes
      let values = [];
      for (let p of s.values())
      {
        values.push(
        arr[p.first][p.second]);
         
      }
         values.sort(function(a,b){return a-b;});
         
      // Largest value in the
      // values vector
      let max =Math.max(...values);
       
              
      // Evaluate minimum increments
      // required to make all vector
      // elements equal
      for (let k = 1;
               k < values.length; k++)
      {
        ans += max - values[k];
      }
    }
  }
    
  // Print the answer
  document.write(ans);
}
 
// Driver Code
let N = 3, M = 3;
let arr=[[1, 2, 1],
                 [3, 4, 1],
                 [1, 2, 1]];
// Function Call
palindromeMatrix(N, M, arr);
 
// This code is contributed by patel2127
</script>

2

Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(1)