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: M = 2, N = 2, mat[M][N] = {{0, 0}, {0, 1}}
Salida: 1
Explicación:
Cambie matrix[0][0] de 0 a 1. El dos caminos de (0, 0) a (1, 1) se vuelven palindrómicos.Entrada: M = 3, N = 7, mat[M][N] = {{1, 2, 3, 4, 5, 6, 7}, {2, 2, 3, 3, 4, 3, 2} , {1, 2, 3, 2, 5, 6, 4}}
Salida: 10
Enfoque ingenuo: para el enfoque ingenuo, consulte este artículo.
Complejidad de tiempo: O(N^3)
Espacio auxiliar: O(N)
Enfoque eficiente:
Se deben hacer las siguientes observaciones:
- Existe una diagonal única para cada valor (i+j) donde i es el índice de fila y j es el índice de columna.
- La tarea se reduce a seleccionar dos diagonales, que están a la misma distancia de la celda (0, 0) y la celda (M – 1, N – 1) respectivamente y hacer que todos sus elementos sean iguales a un solo número, que se repite la mayor cantidad de veces. veces en ambas diagonales elegidas.
- Si el número de elementos entre la celda (0, 0) y (M – 1, N – 1) es impar, entonces existe una diagonal común equidistante de ambas celdas. Los elementos de esa diagonal no necesitan modificarse ya que no afectan la disposición palindrómica de un camino.
- Si el número de celdas entre (0, 0) y (M – 1, N – 1) es par, no existe tal diagonal común.
Siga los pasos a continuación para resolver el problema:
- Cree una array 2D frequency_diagonal que almacene la frecuencia de todos los números en cada diagonal elegida.
- Cada diagonal se puede representar de forma única como la suma de (i, j).
- Inicialice una variable de conteo que almacene el conteo del número total de celdas donde se deben reemplazar los valores.
- Iterar sobre mat[][] e incrementar la frecuencia del elemento actual en la diagonal (valor (i + j)) a la que pertenece.
- Inicialice una variable número_de_elementos en 1, que almacena el número de elementos en cada uno de los pares de diagonales elegidos actualmente.
- Inicialice start = 0 y end = M + N – 2 y repita los pasos a continuación hasta que start < end :
- Encuentre la frecuencia del número que aparece un máximo de veces en las dos diagonales seleccionadas que son equidistantes de (0, 0) y (M-1, N-1) .
- Deje que la frecuencia en el paso anterior sea X . Agregue el valor (número total de elementos en las dos diagonales – X) para contar el número mínimo de cambios.
- Incremente el inicio en 1 y decremente el final en 1 y si el número de elementos en la diagonal actual es menor que el máximo de elementos posibles en cualquier diagonal de la array, entonces incremente número_de_elementos en 1.
- Imprima el valor del recuento total después de los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the minimum
// number of replacements
int MinReplacements(
int M, int N, int mat[][30])
{
// 2D array to store frequency
// of all the numbers in
// each diagonal
int frequency_diagonal[100][10005];
// Initialise all the elements
// of 2D array with 0
memset(frequency_diagonal, 0,
sizeof(frequency_diagonal));
// Initialise answer as 0
int answer = 0;
// Iterate over the matrix
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
// Update the frequency of
// number mat[i][j]
// for the diagonal
// identified by (i+j)
frequency_diagonal[i + j]
[mat[i][j]]++;
}
}
// Initialize start as 0
// which indicates the
// first diagonal
int start = 0;
// Initialize end as
// M + N - 2 which indicates
// the last diagonal
int end = M + N - 2;
// Number of elements in
// the current diagonal
int no_of_elemnts = 1;
// Maximum possible number
// of elements in a diagonal
// can be minimum of (number of
// rows and number of columns)
int max_elements = min(M, N);
while (start < end) {
// The frequency of number
// which occurs for the
// maximum number of times
// in the two selected
// diagonals
int X = INT_MIN;
for (int i = 0; i <= 10000; i++) {
X = max(
X,
frequency_diagonal[start][i]
+ frequency_diagonal[end][i]);
}
answer = answer + (2 * (no_of_elemnts)) - X;
// Increment start
start++;
// Decrement end
end--;
// Increment current number
// of elements until it reaches
// the maximum possible value
if (no_of_elemnts < max_elements)
no_of_elemnts++;
}
// return the final answer
return answer;
}
// Driver Code
int main()
{
// Number of rows
int M = 3;
// Number of columns
int N = 7;
int mat[30][30]
= { { 1, 2, 3, 4, 5, 6, 7 },
{ 2, 2, 3, 3, 4, 3, 2 },
{ 1, 2, 3, 2, 5, 6, 4 } };
cout << MinReplacements(M, N, mat)
<< endl;
}
Java
// Java program of the above approach
class GFG{
// Function to calculate the minimum
// number of replacements
static int MinReplacements(int M, int N,
int mat[][])
{
// 2D array to store frequency
// of all the numbers in
// each diagonal
int [][]frequency_diagonal = new int[100][10005];
// Initialise answer as 0
int answer = 0;
// Iterate over the matrix
for(int i = 0; i < M; i++)
{
for(int j = 0; j < N; j++)
{
// Update the frequency of
// number mat[i][j]
// for the diagonal
// identified by (i+j)
frequency_diagonal[i + j][mat[i][j]]++;
}
}
// Initialize start as 0
// which indicates the
// first diagonal
int start = 0;
// Initialize end as
// M + N - 2 which indicates
// the last diagonal
int end = M + N - 2;
// Number of elements in
// the current diagonal
int no_of_elemnts = 1;
// Maximum possible number
// of elements in a diagonal
// can be minimum of (number of
// rows and number of columns)
int max_elements = Math.min(M, N);
while (start < end)
{
// The frequency of number
// which occurs for the
// maximum number of times
// in the two selected
// diagonals
int X = Integer.MIN_VALUE;
for(int i = 0; i <= 10000; i++)
{
X = Math.max(X,
frequency_diagonal[start][i] +
frequency_diagonal[end][i]);
}
answer = answer + (2 * (no_of_elemnts)) - X;
// Increment start
start++;
// Decrement end
end--;
// Increment current number
// of elements until it reaches
// the maximum possible value
if (no_of_elemnts < max_elements)
no_of_elemnts++;
}
// return the final answer
return answer;
}
// Driver Code
public static void main(String[] args)
{
// Number of rows
int M = 3;
// Number of columns
int N = 7;
int mat[][] = { { 1, 2, 3, 4, 5, 6, 7 },
{ 2, 2, 3, 3, 4, 3, 2 },
{ 1, 2, 3, 2, 5, 6, 4 } };
System.out.print(MinReplacements(M, N, mat) + "\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program of the above approach import sys # Function to calculate the minimum # number of replacements def MinReplacements(M, N, mat): # 2D array to store frequency # of all the numbers in # each diagonal frequency_diagonal = [[0 for x in range(10005)] for y in range (100)]; # Initialise answer as 0 answer = 0 # Iterate over the matrix for i in range(M): for j in range(N): # Update the frequency of # number mat[i][j] # for the diagonal # identified by (i+j) frequency_diagonal[i + j][mat[i][j]] += 1 # Initialize start as 0 # which indicates the # first diagonal start = 0 # Initialize end as # M + N - 2 which indicates # the last diagonal end = M + N - 2 # Number of elements in # the current diagonal no_of_elemnts = 1 # Maximum possible number # of elements in a diagonal # can be minimum of (number of # rows and number of columns) max_elements = min(M, N) while (start < end): # The frequency of number # which occurs for the # maximum number of times # in the two selected # diagonals X = -sys.maxsize - 1 for i in range(10001): X = max(X, frequency_diagonal[start][i] + frequency_diagonal[end][i]) answer = answer + (2 * (no_of_elemnts)) - X # Increment start start += 1 # Decrement end end -= 1 # Increment current number # of elements until it reaches # the maximum possible value if (no_of_elemnts < max_elements): no_of_elemnts += 1 # Return the final answer return answer # Driver Code # Number of rows M = 3 # Number of columns N = 7 mat = [ [ 1, 2, 3, 4, 5, 6, 7 ], [ 2, 2, 3, 3, 4, 3, 2 ], [ 1, 2, 3, 2, 5, 6, 4 ] ] print(MinReplacements(M, N, mat)) # This code is contributed by chitranayal
C#
// C# program of the above approach
using System;
class GFG{
// Function to calculate the minimum
// number of replacements
static int MinReplacements(int M, int N,
int [,]mat)
{
// 2D array to store frequency
// of all the numbers in
// each diagonal
int [,]frequency_diagonal = new int[100, 10005];
// Initialise answer as 0
int answer = 0;
// Iterate over the matrix
for(int i = 0; i < M; i++)
{
for(int j = 0; j < N; j++)
{
// Update the frequency of
// number mat[i,j]
// for the diagonal
// identified by (i+j)
frequency_diagonal[i + j, mat[i, j]]++;
}
}
// Initialize start as 0
// which indicates the
// first diagonal
int start = 0;
// Initialize end as
// M + N - 2 which indicates
// the last diagonal
int end = M + N - 2;
// Number of elements in
// the current diagonal
int no_of_elemnts = 1;
// Maximum possible number
// of elements in a diagonal
// can be minimum of (number of
// rows and number of columns)
int max_elements = Math.Min(M, N);
while (start < end)
{
// The frequency of number
// which occurs for the
// maximum number of times
// in the two selected
// diagonals
int X = int.MinValue;
for(int i = 0; i <= 10000; i++)
{
X = Math.Max(X,
frequency_diagonal[start, i] +
frequency_diagonal[end, i]);
}
answer = answer + (2 * (no_of_elemnts)) - X;
// Increment start
start++;
// Decrement end
end--;
// Increment current number
// of elements until it reaches
// the maximum possible value
if (no_of_elemnts < max_elements)
no_of_elemnts++;
}
// Return the readonly answer
return answer;
}
// Driver Code
public static void Main(String[] args)
{
// Number of rows
int M = 3;
// Number of columns
int N = 7;
int [,]mat = { { 1, 2, 3, 4, 5, 6, 7 },
{ 2, 2, 3, 3, 4, 3, 2 },
{ 1, 2, 3, 2, 5, 6, 4 } };
Console.Write(MinReplacements(M, N, mat) + "\n");
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// Javascript program of the above approach
// Function to calculate the minimum
// number of replacements
function MinReplacements(M,N,mat)
{
// 2D array to store frequency
// of all the numbers in
// each diagonal
let frequency_diagonal = new Array(100);
for(let i=0;i<100;i++)
{
frequency_diagonal[i]=new Array(10005);
for(let j=0;j<10005;j++)
{
frequency_diagonal[i][j]=0;
}
}
// Initialise answer as 0
let answer = 0;
// Iterate over the matrix
for(let i = 0; i < M; i++)
{
for(let j = 0; j < N; j++)
{
// Update the frequency of
// number mat[i][j]
// for the diagonal
// identified by (i+j)
frequency_diagonal[i + j][mat[i][j]]++;
}
}
// Initialize start as 0
// which indicates the
// first diagonal
let start = 0;
// Initialize end as
// M + N - 2 which indicates
// the last diagonal
let end = M + N - 2;
// Number of elements in
// the current diagonal
let no_of_elemnts = 1;
// Maximum possible number
// of elements in a diagonal
// can be minimum of (number of
// rows and number of columns)
let max_elements = Math.min(M, N);
while (start < end)
{
// The frequency of number
// which occurs for the
// maximum number of times
// in the two selected
// diagonals
let X = Number.MIN_VALUE;
for(let i = 0; i <= 10000; i++)
{
X = Math.max(X,
frequency_diagonal[start][i] +
frequency_diagonal[end][i]);
}
answer = answer + (2 * (no_of_elemnts)) - X;
// Increment start
start++;
// Decrement end
end--;
// Increment current number
// of elements until it reaches
// the maximum possible value
if (no_of_elemnts < max_elements)
no_of_elemnts++;
}
// return the final answer
return answer;
}
// Driver Code
// Number of rows
let M = 3;
// Number of columns
let N = 7;
let mat = [[ 1, 2, 3, 4, 5, 6, 7 ],
[ 2, 2, 3, 3, 4, 3, 2 ],
[ 1, 2, 3, 2, 5, 6, 4 ]];
document.write(MinReplacements(M, N, mat) + "<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
10
Complejidad de Tiempo: O(M * N)
Espacio Auxiliar: O(M * N)
Publicación traducida automáticamente
Artículo escrito por mohitkumarbt2k18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA