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 el cada camino para ser palindrómico.
Eso es => mat[1][1] = 1
Caminos => {1, 2, 1}, {1, 3, 1}
Enfoque sencillo:
La observación clave en el problema es que los elementos a la misma distancia del extremo delantero o trasero son iguales. Por lo tanto, encuentre todos los elementos a la misma distancia de (0, 0) y (N-1, M-1) y luego hágalos iguales en un número mínimo de cambios. Mantenga una variable de conteo para obtener el número total de cambios. A continuación se muestra la ilustración del enfoque:
- La distancia posible desde la parte superior izquierda y la parte inferior derecha es 0 a N + M – 2.
- Mantenga dos punteros, uno en la parte superior izquierda que es la distancia en 0 y otro en N + M – 2.
- Iterar sobre la array y para todas las distancias mantener un mapa hash de los elementos de la array a la distancia actual.
- Actualice los elementos de la array con el número mínimo de cambios necesarios.
- Finalmente, incremente la distancia izquierda en 1 y disminuya la distancia derecha en 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// minimum number of changes required
// such that every path from top left
// to the bottom right
// are palindromic paths
#include <bits/stdc++.h>
using namespace std;
#define M 3
#define N 3
// Function to find the minimum number
// of the changes required for the
// every path to be palindromic
int minchanges(int mat[N][M])
{
// count variable for
// maintaining total changes.
int count = 0;
// left and right variables for
// keeping distance values
// from cell(0, 0) and
// (N-1, M-1) respectively.
int left = 0, right = N + M - 2;
while (left < right) {
unordered_map<int, int> mp;
int totalsize = 0;
// Iterating over the matrix
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (i + j == left) {
mp[mat[i][j]]++;
totalsize++;
}
else if (i + j == right) {
mp[mat[i][j]]++;
totalsize++;
}
}
}
// Finding minimum number
// of changes required.
unordered_map<int, int>::iterator itr = mp.begin();
int changes = 0;
for (; itr != mp.end(); itr++)
changes = max(changes, itr->second);
// Minimum no. of changes will
// be the minimum no.
// of different values and
// we will assume to
// make them equals to value
// with maximum frequency element
count += totalsize - changes;
// Moving ahead with
// greater distance
left++;
right--;
}
return count;
}
// Drive Code
int main()
{
int mat[][M]
= { { 1, 4, 1 }, { 2, 5, 3 }, { 1, 3, 1 } };
// Function Call
cout << minchanges(mat);
return 0;
}
Java
// Java implementation to find the
// minimum number of changes required
// such that every path from top left
// to the bottom right are palindromic
// paths
import java.io.*;
import java.util.*;
class GFG {
static final int M = 3;
static final int N = 3;
// Function to find the minimum number
// of the changes required for the
// every path to be palindromic
static int minchanges(int[][] mat)
{
// count variable for
// maintaining total changes.
int count = 0;
// left and right variables for
// keeping distance values
// from cell(0, 0) and
// (N-1, M-1) respectively.
int left = 0, right = N + M - 2;
while (left < right) {
Map<Integer, Integer> mp = new HashMap<>();
int totalsize = 0;
// Iterating over the matrix
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (i + j == left) {
mp.put(mat[i][j],
mp.getOrDefault(mat[i][j], 0)
+ 1);
totalsize++;
}
else if (i + j == right) {
mp.put(mat[i][j],
mp.getOrDefault(mat[i][j], 0)
+ 1);
totalsize++;
}
}
}
// Finding minimum number
// of changes required.
int changes = 0;
for (Map.Entry<Integer, Integer> itr :
mp.entrySet())
changes = Math.max(changes, itr.getValue());
// Minimum no. of changes will
// be the minimum no.
// of different values and
// we will assume to
// make them equals to value
// with maximum frequency element
count += totalsize - changes;
// Moving ahead with
// greater distance
left++;
right--;
}
return count;
}
// Driver Code
public static void main(String[] args)
{
int mat[][]
= { { 1, 4, 1 }, { 2, 5, 3 }, { 1, 3, 1 } };
// Function Call
System.out.println(minchanges(mat));
}
}
// This code is contributed by offbeat
Python3
# Python3 implementation to find the
# minimum number of changes required
# such that every path from top left
# to the bottom right
# are palindromic paths
M = 3
N = 3
# Function to find the minimum number
# of the changes required for the
# every path to be palindromic
def minchanges(mat):
# count variable for
# maintaining total changes.
count = 0
# left and right variables for
# keeping distance values
# from cell(0, 0) and
# (N-1, M-1) respectively.
left = 0
right = N + M - 2
while (left < right):
mp = {}
totalsize = 0
# Iterating over the matrix
for i in range(N):
for j in range(M):
if (i + j == left):
mp[mat[i][j]] =
mp.get(mat[i][j], 0) + 1
totalsize += 1
elif (i + j == right):
mp[mat[i][j]] =
mp.get(mat[i][j], 0) + 1
totalsize += 1
# Finding minimum number
# of changes required.
changes = 0
for itr in mp:
changes = max(changes, mp[itr])
# Minimum no. of changes will
# be the minimum no.
# of different values and
# we will assume to
# make them equals to value
# with maximum frequency element
count += totalsize - changes
# Moving ahead with
# greater distance
left += 1
right -= 1
return count
# Driver Code
if __name__ == '__main__':
mat = [[1, 4, 1],
[2, 5, 3],
[1, 3, 1]]
# Function Call
print(minchanges(mat))
# This code is contributed by Mohit Kumar 29
C#
// C# implementation to find the
// minimum number of changes required
// such that every path from top left
// to the bottom right are palindromic
// paths
using System;
using System.Collections;
using System.Collections.Generic;
class GFG {
static int M = 3;
static int N = 3;
// Function to find the minimum number
// of the changes required for the
// every path to be palindromic
static int minchanges(int[, ] mat)
{
// count variable for
// maintaining total changes.
int count = 0;
// left and right variables for
// keeping distance values
// from cell(0, 0) and
// (N-1, M-1) respectively.
int left = 0, right = N + M - 2;
while (left < right) {
Dictionary<int, int> mp
= new Dictionary<int, int>();
int totalsize = 0;
// Iterating over the matrix
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (i + j == left) {
if (mp.ContainsKey(mat[i, j])) {
mp[mat[i, j]]++;
}
else {
mp[mat[i, j]] = 1;
}
totalsize++;
}
else if (i + j == right) {
if (mp.ContainsKey(mat[i, j])) {
mp[mat[i, j]]++;
}
else {
mp[mat[i, j]] = 1;
}
totalsize++;
}
}
}
// Finding minimum number
// of changes required.
int changes = 0;
foreach(KeyValuePair<int, int> itr in mp)
{
changes = Math.Max(changes, itr.Value);
}
// Minimum no. of changes will
// be the minimum no.
// of different values and
// we will assume to
// make them equals to value
// with maximum frequency element
count += totalsize - changes;
// Moving ahead with
// greater distance
left++;
right--;
}
return count;
}
// Driver Code
public static void Main(string[] args)
{
int[, ] mat
= { { 1, 4, 1 }, { 2, 5, 3 }, { 1, 3, 1 } };
// Function Call
Console.Write(minchanges(mat));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript implementation to find the
// minimum number of changes required
// such that every path from top left
// to the bottom right
// are palindromic paths
var M = 3
var N = 3;
// Function to find the minimum number
// of the changes required for the
// every path to be palindromic
function minchanges(mat)
{
// count variable for
// maintaining total changes.
var count = 0;
// left and right variables for
// keeping distance values
// from cell(0, 0) and
// (N-1, M-1) respectively.
var left = 0, right = N + M - 2;
while (left < right) {
var mp = new Map();
var totalsize = 0;
// Iterating over the matrix
for (var i = 0; i < N; i++) {
for (var j = 0; j < M; j++) {
if (i + j == left || i + j == right) {
if(mp.has(mat[i][j]))
mp.set(mat[i][j], mp.get(mat[i][j])+1)
else
mp.set(mat[i][j], 1)
totalsize++;
}
}
}
var changes = 0;
// Finding minimum number
// of changes required.
mp.forEach((value, key) => {
changes = Math.max(changes, value);
});
// Minimum no. of changes will
// be the minimum no.
// of different values and
// we will assume to
// make them equals to value
// with maximum frequency element
count += totalsize - changes;
// Moving ahead with
// greater distance
left++;
right--;
}
return count;
}
// Drive Code
var mat
= [ [ 1, 4, 1 ], [ 2, 5, 3 ], [ 1, 3, 1 ] ];
// Function Call
document.write( minchanges(mat));
// This code is contributed by importantly.
</script>
Producción:
2
Análisis de rendimiento:
- Complejidad temporal: O(N 3 )
- Espacio Auxiliar: O(N)
Enfoque eficiente:
Algoritmo:
- Usaremos un hashmap para contar la frecuencia de cada elemento que está a la misma distancia de la parte superior e inferior.
- Usaremos un mapa 2D para esto donde la clave será el índice y el valor será otro mapa que contará la frecuencia.
- Después de contar la frecuencia, iteramos de l=0 a r=m+n-1 mientras que l<r y cada vez contaremos la suma y encontraremos el valor de frecuencia máxima ≥f
- Reemplazaremos los elementos (sum-f) con el elemento cuya frecuencia sea máxima y almacenaremos result+=(sum-f)
- Imprimir resultado
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to count minimum change
// required to convert all the paths
// pallindromic from top left to
// right bottom cell.
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of the changes required for the
// every path to be palindromic
int minchanges(vector<vector<int> >& a)
{
int res = 0; // use to store final result
// Row and column
int N = a.size(), M = a[0].size();
// mp_key -> (i+j) , mp_value -> nw_map
// nw_map_key -> elements_of_matrix
// nw_map_value -> frequency of elements
// 2-D map
map<int, map<int, int> > mp;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// calculating position
int ind = i + j;
// increase the frequency of a[i][j]
// at position ind
mp[ind][a[i][j]]++;
}
}
// Define left and right limit
int r = M + N - 2, l = 0;
while (l < r) {
// s-> count total number of elements
// at index l and r
// mx-> store maximum frequency of any element
int s = 0, mx = 0;
// store all elements frequency at index l
for (auto x : mp[r]) {
mp[l][x.first] += x.second;
}
// Count total elements and mx->max_frequency
for (auto x : mp[l]) {
s += x.second;
mx = max(x.second, mx);
}
// We will replace (s-mx) elements with
// the element whose frequency is mx
res += (s - mx);
l++;
r--;
}
// return res
return res;
}
// Driver Code
int main()
{
// Function Call
vector<vector<int> > mat
= { { 1, 4, 1 }, { 2, 5, 3 }, { 1, 3, 1 } };
cout << "Total number of changes requires "
<< minchanges(mat) << "\n";
// Function Call
vector<vector<int> > mat1
= { { 1, 4 }, { 2, 5 }, { 1, 3 }, { 2, 5 } };
cout << "Total number of changes requires "
<< minchanges(mat1) << "\n";
return 0;
}
// This code is contributed by ajaykr00kj
Producción
Total number of changes requires 2 Total number of changes requires 3
Complejidad del tiempo: O(m*n)
Complejidad espacial: O(m*n)
Publicación traducida automáticamente
Artículo escrito por pradyumanagarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA