Dada una array con N filas y M columnas, la tarea es encontrar los reemplazos mínimos necesarios para hacer palindrómicas todas las filas y columnas de una array dada .
Ejemplos:
Entrada: a[][] = {{1, 2, 3}, {4, 5, 3}, {1, 2, 1}}
Salida: 2
Explicación: Para hacer palindrómica la array dada, reemplace a[0] [2] por 1 y reemplaza a[1][2] por 4 .Entrada: a[][] = {{1, 2, 4}, {4, 5, 6}}
Salida: 3
Explicación: Para hacer palindrómica una array dada, reemplace a[0][0] por 4 , a[ 1][2] por 4 y a[[0][1] por 5 .
Enfoque: La idea es seleccionar el conjunto de cuatro celdas de la array como se explica a continuación y proceder en consecuencia.
- Para hacer que cada fila y cada columna de la array sean palindrómicas, recorra la array dada, y para cada celda (i, j) (i = [0, N/2], j = [0, M/2]), seleccione un conjunto de las siguientes cuatro celdas:
- Haga que el valor de todas estas cuatro celdas sea igual al valor más frecuente entre las cuatro. Cuente los reemplazos así requeridos.
- Después de completar los pasos anteriores, imprima el recuento de reemplazos realizados.
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 count minimum
// changes to make the matrix
// palindromic
int minchanges(vector<vector<int> > mat)
{
// Rows in the matrix
int N = mat.size();
// Columns in the matrix
int M = mat[0].size();
int i, j, ans = 0, x;
map<int, int> mp;
// Traverse the given matrix
for (i = 0; i < N / 2; i++) {
for (j = 0; j < M / 2; j++) {
// Store the frequency of
// the four cells
mp[mat[i][M - 1 - j]]++;
mp[mat[i][j]]++;
mp[mat[N - 1 - i][M - 1 - j]]++;
mp[mat[N - 1 - i][j]]++;
x = 0;
// Iterate over the map
for (auto it = mp.begin();
it != mp.end(); it++) {
x = max(x, it->second);
}
// Min changes to do to make all
ans = ans + 4 - x;
// Four elements equal
mp.clear();
}
}
// Make the middle row palindromic
if (N % 2 == 1) {
for (i = 0; i < M / 2; i++) {
if (mat[N / 2][i]
!= mat[N / 2][M - 1 - i])
ans++;
}
}
if (M % 2 == 1) {
for (i = 0; i < N / 2; i++) {
// Make the middle column
// palindromic
if (mat[i][M / 2]
!= mat[N - 1 - i][M / 2])
ans++;
}
}
// Print minimum changes
cout << ans;
}
// Driver Code
int main()
{
// Given matrix
vector<vector<int> > mat{ { 1, 2, 3 },
{ 4, 5, 3 },
{ 1, 2, 1 } };
// Function Call
minchanges(mat);
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to count minimum
// changes to make the matrix
// palindromic
static void minchanges(int [][]mat)
{
// Rows in the matrix
int N = mat.length;
// Columns in the matrix
int M = mat[0].length;
int i, j, ans = 0, x;
HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();
// Traverse the given matrix
for (i = 0; i < N / 2; i++)
{
for (j = 0; j < M / 2; j++)
{
// Store the frequency of
// the four cells
if(mp.containsKey(mat[i][M - 1 - j]))
{
mp.put(mat[i][M - 1 - j],
mp.get(mat[i][M - 1 - j]) + 1);
}
else
{
mp.put(mat[i][M - 1 - j], 1);
}
if(mp.containsKey(mat[i][j]))
{
mp.put(mat[i][j], mp.get(mat[i][j]) + 1);
}
else
{
mp.put(mat[i][j], 1);
}
if(mp.containsKey(mat[N - 1 - i][M - 1 - j]))
{
mp.put(mat[N - 1 - i][M - 1 - j],
mp.get(mat[N - 1 - i][M - 1 - j]) + 1);
}
else
{
mp.put(mat[N - 1 - i][M - 1 - j], 1);
}
if(mp.containsKey(mat[N - 1 - i][j]))
{
mp.put(mat[N - 1 - i][j],
mp.get(mat[N - 1 - i][j])+1);
}
else
{
mp.put(mat[N - 1 - i][j], 1);
}
x = 0;
// Iterate over the map
for (Map.Entry<Integer,Integer> it : mp.entrySet())
{
x = Math.max(x, it.getValue());
}
// Min changes to do to make all
ans = ans + 4 - x;
// Four elements equal
mp.clear();
}
}
// Make the middle row palindromic
if (N % 2 == 1)
{
for (i = 0; i < M / 2; i++)
{
if (mat[N / 2][i]
!= mat[N / 2][M - 1 - i])
ans++;
}
}
if (M % 2 == 1)
{
for (i = 0; i < N / 2; i++)
{
// Make the middle column
// palindromic
if (mat[i][M / 2]
!= mat[N - 1 - i][M / 2])
ans++;
}
}
// Print minimum changes
System.out.print(ans);
}
// Driver Code
public static void main(String[] args)
{
// Given matrix
int [][]mat = { { 1, 2, 3 },
{ 4, 5, 3 },
{ 1, 2, 1 } };
// Function Call
minchanges(mat);
}
}
// This code is contributed by shikhasingrajput
Python
# Python program for the above approach
# Function to count minimum
# changes to make the matrix
# palindromic
def minchanges(mat) :
# Rows in the matrix
N = len(mat)
# Columns in the matrix
M = len(mat[0])
ans = 0
mp = {}
# Traverse the given matrix
for i in range(N//2):
for j in range(M//2):
# Store the frequency of
# the four cells
mp[mat[i][M - 1 - j]] = mp.get(mat[i][M - 1 - j], 0) + 1
mp[mat[i][j]] = mp.get(mat[i][j], 0) + 1
mp[mat[N - 1 - i][M - 1 - j]] = mp.get(mat[N - 1 - i][M - 1 - j], 0) + 1
mp[mat[N - 1 - i][j]] = mp.get(mat[N - 1 - i][j], 0) + 1
x = 0
# Iterate over the map
for it in mp:
x = max(x, mp[it])
# Min changes to do to make all
ans = ans + 4 - x
# Four elements equal
mp.clear()
# Make the middle row palindromic
if (N % 2 == 1) :
for i in range(M // 2):
if (mat[N // 2][i]
!= mat[N // 2][M - 1 - i]) :
ans += 1
if (M % 2 == 1) :
for i in range(N // 2):
# Make the middle column
# palindromic
if (mat[i][M // 2]
!= mat[N - 1 - i][M // 2]):
ans += 1
# Print minimum changes
print(ans)
# Driver Code
# Given matrix
mat = [[ 1, 2, 3 ],
[ 4, 5, 3 ],
[1, 2, 1 ]]
# Function Call
minchanges(mat)
# This code is contributed by susmitakundugoaldanga
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to count minimum
// changes to make the matrix
// palindromic
static void minchanges(int [,]mat)
{
// Rows in the matrix
int N = mat.GetLength(0);
// Columns in the matrix
int M = mat.GetLength(1);
int i, j, ans = 0, x;
Dictionary<int,int> mp = new Dictionary<int,int>();
// Traverse the given matrix
for (i = 0; i < N / 2; i++)
{
for (j = 0; j < M / 2; j++)
{
// Store the frequency of
// the four cells
if(mp.ContainsKey(mat[i,M - 1 - j]))
{
mp[mat[i,M - 1 - j]]=
mp[mat[i,M - 1 - j]] + 1;
}
else
{
mp.Add(mat[i,M - 1 - j], 1);
}
if(mp.ContainsKey(mat[i,j]))
{
mp[mat[i,j]] = mp[mat[i,j]] + 1;
}
else
{
mp.Add(mat[i,j], 1);
}
if(mp.ContainsKey(mat[N - 1 - i,M - 1 - j]))
{
mp[mat[N - 1 - i,M - 1 - j]]=
mp[mat[N - 1 - i,M - 1 - j]] + 1;
}
else
{
mp.Add(mat[N - 1 - i,M - 1 - j], 1);
}
if(mp.ContainsKey(mat[N - 1 - i,j]))
{
mp[mat[N - 1 - i,j]] =
mp[mat[N - 1 - i,j]]+1;
}
else
{
mp.Add(mat[N - 1 - i,j], 1);
}
x = 0;
// Iterate over the map
foreach (KeyValuePair<int,int> it in mp)
{
x = Math.Max(x, it.Value);
}
// Min changes to do to make all
ans = ans + 4 - x;
// Four elements equal
mp.Clear();
}
}
// Make the middle row palindromic
if (N % 2 == 1)
{
for (i = 0; i < M / 2; i++)
{
if (mat[N / 2,i]
!= mat[N / 2,M - 1 - i])
ans++;
}
}
if (M % 2 == 1)
{
for (i = 0; i < N / 2; i++)
{
// Make the middle column
// palindromic
if (mat[i,M / 2]
!= mat[N - 1 - i,M / 2])
ans++;
}
}
// Print minimum changes
Console.Write(ans);
}
// Driver Code
public static void Main(String[] args)
{
// Given matrix
int [,]mat = { { 1, 2, 3 },
{ 4, 5, 3 },
{ 1, 2, 1 } };
// Function Call
minchanges(mat);
}
}
// This code contributed by shikhasingrajput
Javascript
<script>
// JavaScript program for the above approach
// Function to count minimum
// changes to make the matrix
// palindromic
function minchanges(mat) {
// Rows in the matrix
var N = mat.length;
// Columns in the matrix
var M = mat[0].length;
var i,
j,
ans = 0,
x;
var mp = {};
// Traverse the given matrix
for (i = 0; i < parseInt(N / 2); i++) {
for (j = 0; j < parseInt(M / 2); j++) {
// Store the frequency of
// the four cells
if (mp.hasOwnProperty(mat[i][M - 1 - j])) {
mp[mat[i][M - 1 - j]] = mp[mat[i][M - 1 - j]] + 1;
}
else {
mp[mat[i][M - 1 - j]] = 1;
}
if (mp.hasOwnProperty(mat[i][j])) {
mp[mat[(i, j)]] = mp[mat[i][j]] + 1;
}
else {
mp[mat[i][j]] = 1;
}
if (mp.hasOwnProperty(mat[N - 1 - i][M - 1 - j])) {
mp[mat[N - 1 - i][M - 1 - j]] = mp[mat[N - 1 - i][M - 1 - j]] + 1;
}
else {
mp[mat[N - 1 - i][M - 1 - j]] = 1;
}
if (mp.hasOwnProperty(mat[N - 1 - i][j])) {
mp[mat[N - 1 - i][j]] = mp[mat[N - 1 - i][j]] + 1;
}
else {
mp[mat[(N - 1 - i, j)]] = 1;
}
x = 0;
// Iterate over the map
for (const [key, value] of Object.entries(mp)) {
x = Math.max(x, value);
}
// Min changes to do to make all
ans = ans + 4 - x;
// Four elements equal
mp = {};
}
}
// Make the middle row palindromic
if (N % 2 === 1) {
for (i = 0; i < parseInt(M / 2); i++) {
if (mat[parseInt(N / 2)][i] !=
mat[parseInt(N / 2)][M - 1 - i])
ans++;
}
}
if (M % 2 === 1) {
for (i = 0; i < parseInt(N / 2); i++) {
// Make the middle column
// palindromic
if (mat[i][parseInt(M / 2)] !=
mat[N - 1 - i][parseInt(M / 2)])
ans++;
}
}
// Print minimum changes
document.write(ans);
}
// Driver Code
// Given matrix
var mat = [
[1, 2, 3],
[4, 5, 3],
[1, 2, 1],
];
// Function Call
minchanges(mat);
</script>
Producción:
2
Complejidad temporal: O(N × M)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por varuntak22 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA