Dada una array con N filas y M columnas, la tarea es hacer todos los caminos posibles desde la celda (N, M) al palíndromo (1, 1) mediante cambios mínimos en los valores de la celda.
Los movimientos posibles desde cualquier celda (x, y) son mover hacia la izquierda (x – 1, y) o hacia abajo (x, y – 1) .
Ejemplos:
Entrada: mat[ ][ ] = { { 1, 2, 2 }, { 1, 0, 0 } }
Salida: 3
Explicación:
Para que cada camino en matrix sea Palindrome, las arrays posibles (después de los cambios) son
{ { 0, 2, 2 }, { 2, 2, 0 } } o { { 1, 2, 2 }, { 2, 2, 1 } }.
Entrada: mat[ ][ ] = { { 5, 3 }, { 0, 5 } }
Salida: 0
Explicación:
No se requieren cambios en la array anterior. Cada camino de (N, M) a (1, 1) ya es Palíndromo
Acercarse:
- Un camino se llama palindrómico si el valor de la última celda es igual al valor de la primera celda, el valor de la penúltima celda es igual al valor de la segunda celda, y así sucesivamente.
- Entonces podemos concluir que, para hacer un camino palindrómico, las celdas a la distancia ( distancia de Manhattan ) x de (N, M) deben ser iguales a las celdas a la distancia x de (1, 1) .
- Para minimizar el número de cambios, convierta cada celda a la distancia x de (1, 1) y (N, M) al más frecuente entre todos los valores presentes en esas celdas.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ Program to implement the
// above approach
#include <bits/stdc++.h>
using namespace std;
#define N 7
// Function for counting changes
int countChanges(int matrix[][N],
int n, int m)
{
// Maximum distance possible
// is (n - 1 + m - 1)
int dist = n + m - 1;
// Stores the maximum element
int Max_element = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Update the maximum
Max_element = max(Max_element,
matrix[i][j]);
}
}
// Stores frequencies of
// values for respective
// distances
int freq[dist][Max_element + 1];
// Initialize frequencies of
// cells as 0
for (int i = 0; i < dist; i++) {
for (int j = 0; j < Max_element + 1;
j++)
freq[i][j] = 0;
}
// Count frequencies of cell
// values in the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Increment frequency of
// value at distance i+j
freq[i + j][matrix[i][j]]++;
}
}
int min_changes_sum = 0;
for (int i = 0; i < dist / 2; i++) {
// Store the most frequent
// value at i-th distance
// from (0, 0) and (N - 1, M - 1)
int maximum = 0;
int total_values = 0;
// Calculate max frequency
// and total cells at distance i
for (int j = 0; j < Max_element + 1;
j++) {
maximum
= max(maximum,
freq[i][j]
+ freq[n + m - 2
- i][j]);
total_values
+= freq[i][j]
+ freq[n + m - 2 - i][j];
}
// Count changes required
// to convert all cells
// at i-th distance to
// most frequent value
min_changes_sum
+= total_values - maximum;
}
return min_changes_sum;
}
// Driver Code
int main()
{
int mat[][N] = { { 7, 0, 3, 1, 8, 1, 3 },
{ 0, 4, 0, 1, 0, 4, 0 },
{ 3, 1, 8, 3, 1, 0, 7 } };
int minChanges = countChanges(mat, 3, 7);
cout << minChanges;
return 0;
}
Java
// Java program to implement the
// above approach
import java.util.*;
class GFG{
static int N = 7;
// Function for counting changes
static int countChanges(int matrix[][],
int n, int m)
{
// Maximum distance possible
// is (n - 1 + m - 1)
int i, j, dist = n + m - 1;
// Stores the maximum element
int Max_element = 0;
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
// Update the maximum
Max_element = Math.max(Max_element,
matrix[i][j]);
}
}
// Stores frequencies of
// values for respective
// distances
int freq[][] = new int[dist][Max_element + 1];
// Initialize frequencies of
// cells as 0
for(i = 0; i < dist; i++)
{
for(j = 0; j < Max_element + 1;
j++)
freq[i][j] = 0;
}
// Count frequencies of cell
// values in the matrix
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
// Increment frequency of
// value at distance i+j
freq[i + j][matrix[i][j]]++;
}
}
int min_changes_sum = 0;
for(i = 0; i < dist / 2; i++)
{
// Store the most frequent
// value at i-th distance
// from (0, 0) and (N - 1, M - 1)
int maximum = 0;
int total_values = 0;
// Calculate max frequency
// and total cells at distance i
for(j = 0; j < Max_element + 1; 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];
}
// Count changes required
// to convert all cells
// at i-th distance to
// most frequent value
min_changes_sum += total_values -
maximum;
}
return min_changes_sum;
}
// Driver Code
public static void main (String []args)
{
int mat[][] = { { 7, 0, 3, 1, 8, 1, 3 },
{ 0, 4, 0, 1, 0, 4, 0 },
{ 3, 1, 8, 3, 1, 0, 7 } };
int minChanges = countChanges(mat, 3, 7);
System.out.print(minChanges);
}
}
// This code is contributed by chitranayal
Python3
# Python3 program to implement the # above approach # Function for counting changes def countChanges(matrix, n, m): # Maximum distance possible # is (n - 1 + m - 1) dist = n + m - 1 # Stores the maximum element Max_element = 0 for i in range(n): for j in range(m): # Update the maximum Max_element = max(Max_element, matrix[i][j]) # Stores frequencies of # values for respective # distances freq = [[0 for i in range(Max_element + 1)] for j in range(dist)] # Initialize frequencies of # cells as 0 for i in range(dist): for j in range(Max_element + 1): freq[i][j] = 0 # Count frequencies of cell # values in the matrix for i in range(n): for j in range(m): # Increment frequency of # value at distance i+j freq[i + j][matrix[i][j]] += 1 min_changes_sum = 0 for i in range(dist // 2): # Store the most frequent # value at i-th distance # from (0, 0) and (N - 1, M - 1) maximum = 0 total_values = 0 # Calculate max frequency # and total cells at distance i for j in range(Max_element + 1): maximum = max(maximum, freq[i][j] + freq[n + m - 2 - i][j]) total_values += (freq[i][j] + freq[n + m - 2 - i][j]) # Count changes required # to convert all cells # at i-th distance to # most frequent value min_changes_sum += total_values - maximum return min_changes_sum # Driver code if __name__ == '__main__': mat = [ [ 7, 0, 3, 1, 8, 1, 3 ], [ 0, 4, 0, 1, 0, 4, 0 ], [ 3, 1, 8, 3, 1, 0, 7 ] ] minChanges = countChanges(mat, 3, 7) print(minChanges) # This code is contributed by Shivam Singh
C#
// C# program to implement the
// above approach
using System;
class GFG{
//static int N = 7;
// Function for counting changes
static int countChanges(int [,]matrix,
int n, int m)
{
// Maximum distance possible
// is (n - 1 + m - 1)
int i, j, dist = n + m - 1;
// Stores the maximum element
int Max_element = 0;
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
// Update the maximum
Max_element = Math.Max(Max_element,
matrix[i, j]);
}
}
// Stores frequencies of
// values for respective
// distances
int [,]freq = new int[dist, Max_element + 1];
// Initialize frequencies of
// cells as 0
for(i = 0; i < dist; i++)
{
for(j = 0; j < Max_element + 1;
j++)
freq[i, j] = 0;
}
// Count frequencies of cell
// values in the matrix
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
// Increment frequency of
// value at distance i+j
freq[i + j, matrix[i, j]]++;
}
}
int min_changes_sum = 0;
for(i = 0; i < dist / 2; i++)
{
// Store the most frequent
// value at i-th distance
// from (0, 0) and (N - 1, M - 1)
int maximum = 0;
int total_values = 0;
// Calculate max frequency
// and total cells at distance i
for(j = 0; j < Max_element + 1; 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];
}
// Count changes required
// to convert all cells
// at i-th distance to
// most frequent value
min_changes_sum += total_values -
maximum;
}
return min_changes_sum;
}
// Driver Code
public static void Main(String []args)
{
int [,]mat = { { 7, 0, 3, 1, 8, 1, 3 },
{ 0, 4, 0, 1, 0, 4, 0 },
{ 3, 1, 8, 3, 1, 0, 7 } };
int minChanges = countChanges(mat, 3, 7);
Console.Write(minChanges);
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// javascript program to implement
// the above approach
// Function for counting changes
function countChanges(matrix,
n, m)
{
// Maximum distance possible
// is (n - 1 + m - 1)
let i, j, dist = n + m - 1;
// Stores the maximum element
let Max_element = 0;
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
// Update the maximum
Max_element = Math.max(Max_element,
matrix[i][j]);
}
}
// Stores frequencies of
// values for respective
// distances
let freq = new Array(dist);
for (i = 0; i < freq.length; i++) {
freq[i] = new Array(2);
}
// Initialize frequencies of
// cells as 0
for(i = 0; i < dist; i++)
{
for(j = 0; j < Max_element + 1;
j++)
freq[i][j] = 0;
}
// Count frequencies of cell
// values in the matrix
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
// Increment frequency of
// value at distance i+j
freq[i + j][matrix[i][j]]++;
}
}
let min_changes_sum = 0;
for(i = 0; i <Math.floor(dist / 2); i++)
{
// Store the most frequent
// value at i-th distance
// from (0, 0) and (N - 1, M - 1)
let maximum = 0;
let total_values = 0;
// Calculate max frequency
// and total cells at distance i
for(j = 0; j < Max_element + 1; 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];
}
// Count changes required
// to convert all cells
// at i-th distance to
// most frequent value
min_changes_sum += total_values -
maximum;
}
return min_changes_sum;
}
// Driver Code
let mat = [[ 7, 0, 3, 1, 8, 1, 3 ],
[ 0, 4, 0, 1, 0, 4, 0 ],
[ 3, 1, 8, 3, 1, 0, 7 ]];
let minChanges = countChanges(mat, 3, 7);
document.write(minChanges);
// This code is contributed by avijitmondal1998.
</script>
Producción:
6
Complejidad Temporal: O(N * M)
Espacio Auxiliar: O((N + M)*maxm), donde maxm es el máximo elemento presente en la array.
Publicación traducida automáticamente
Artículo escrito por himanshu77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA