dados dos matrices un y b de tamaño Nuevo Méjico . La tarea es encontrar el requerido. número de pasos de transformación para que ambas matrices se vuelvan iguales. Imprimir -1 si esto no es posible.
El transformación el paso es el siguiente:
- Seleccione cualquier matriz entre dos matrices.
- Elija cualquiera de los dos fila/columna de la matriz seleccionada.
- Incrementar cada elemento de la selección. fila/columna por 1.
Ejemplos:
Aporte:
un[][] = [[1 1]
[1 1]]segundo[][] = [[1 2]
[3 4]]Producción : 3
Explicación :
[[1 1] -> [[1 2] -> [[1 2] -> [[1 2]
[1 1]] [1 2]] [2 3]] [3 4]]
Aporte :
un[][] = [[1 1]
[1 0]]segundo[][] = [[1 2]
[3 4]]Producción : -1
Explicación : Ninguna transformación hará que a y b sean iguales.
Acercarse:
La idea es que incrementando cualquier fila/columna en matriz a es equivalente a decreciente la misma fila/columna en matriz b .
Esto significa que en lugar de rastrear ambas matrices podemos trabajar con su diferencia. (a[i][j] - b[i][j]). Cuando incrementamos una fila en ' a' todos los elementos en esa fila aumentan en 1, que es lo mismo que todos los elementos en esa fila de la matriz de diferencias aumentan en 1. De manera similar, cuando incrementamos una columna en ' a' es equivalente a aumentar todos los elementos en esa columna de la matriz de diferencias en 1.
Esto nos permite transformar el problema para trabajar con una sola matriz.
Determinar si existe alguna solución o no:
Después de crear el matriz de diferencias para cada celda a[i][j] (excluyendo la primera fila y la primera columna) comprobamos si
a[i][j] - a[i][0] - a[0][j] + a[0][0] = 0.
Si esta ecuación no se cumple para ninguna celda, podemos concluir inmediatamente que no existe ninguna solución.
¿Por qué funciona esto?
Piensa en como fila y columna Las operaciones afectan a cada celda: cuando realizamos incógnita operaciones en fila i y y operaciones en columna j a[yo][j] cambia por (x + y) un[yo][0] cambia por x (solo operaciones de fila) a[0][j] cambia por y (solo operaciones de columna) y a[0][0] se ve afectado por ni fila i ni columna j operaciones. Por lo tanto (x + y) - x - y + 0 = 0 debe cumplirse para cualquier solución válida. Si esta ecuación no se cumple para ninguna celda, significa que ninguna secuencia de operaciones de filas y columnas puede transformar una matriz en otra.
Calcule el número de transformaciones requeridas:
C++Para calcular el número de transformaciones necesarias sólo necesitamos mirar el primera fila y primera columna porque:
- Primero resumimos |a[i][0]| para todo i (cada primer elemento de columna) porque esto representa cuántas operaciones de fila necesitamos. Para cada fila i necesitamos |a[i][0]| operaciones para hacer que ese elemento de fila sea cero.
- Luego resumimos |a[0][j] - a[0][0]| para todo j (cada elemento de la primera fila menos el primer elemento) porque esto representa operaciones de columna adicionales necesarias. Restamos un[0][0] para evitar contarlo dos veces ya que las operaciones de fila ya han afectado a este elemento.
- La suma de estos dos nos da la número mínimo de operaciones necesario ya que las operaciones de fila manejan las diferencias de la primera columna y las operaciones de columna manejan las diferencias restantes en la primera fila.
// C++ program to find number of transformation // to make two Matrix Equal #include
// Java program to find number of transformation // to make two Matrix Equal import java.util.*; class GfG { static int countOperations(int[][] a int[][] b) { int n = a.length; int m = a[0].length; // Create difference matrix (a = a - b) for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { a[i][j] -= b[i][j]; } } // Check if transformation is possible using the // property a[i][j] - a[i][0] - a[0][j] + a[0][0] // should be 0 for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { if (a[i][j] - a[i][0] - a[0][j] + a[0][0] != 0) { return -1; } } } int result = 0; // Add operations needed for first column for (int i = 0; i < n; i++) { result += Math.abs(a[i][0]); } // Add operations needed for // first row (excluding a[0][0]) for (int j = 0; j < m; j++) { result += Math.abs(a[0][j] - a[0][0]); } return result; } public static void main(String[] args) { int[][] a = { { 1 1 } { 1 1 } }; int[][] b = { { 1 2 } { 3 4 } }; System.out.println(countOperations(a b)); } }
# Python program to find number of transformation # to make two Matrix Equal def countOperations(a b): n = len(a) m = len(a[0]) # Create difference matrix (a = a - b) for i in range(n): for j in range(m): a[i][j] -= b[i][j] # Check if transformation is possible using the property # a[i][j] - a[i][0] - a[0][j] + a[0][0] should be 0 for i in range(1 n): for j in range(1 m): if a[i][j] - a[i][0] - a[0][j] + a[0][0] != 0: return -1 result = 0 # Add operations needed for first column for i in range(n): result += abs(a[i][0]) # Add operations needed for # first row (excluding a[0][0]) for j in range(m): result += abs(a[0][j] - a[0][0]) return result if __name__ == '__main__': a = [ [1 1] [1 1] ] b = [ [1 2] [3 4] ] print(countOperations(a b))
// C# program to find number of transformation // to make two Matrix Equal using System; class GfG { static int countOperations(int[ ] a int[ ] b) { int n = a.GetLength(0); int m = a.GetLength(1); // Create difference matrix (a = a - b) for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { a[i j] -= b[i j]; } } // Check if transformation is possible using the // property a[i j] - a[i 0] - a[0 j] + a[0 0] // should be 0 for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { if (a[i j] - a[i 0] - a[0 j] + a[0 0] != 0) { return -1; } } } int result = 0; // Add operations needed for first column for (int i = 0; i < n; i++) { result += Math.Abs(a[i 0]); } // Add operations needed for // first row (excluding a[0 0]) for (int j = 0; j < m; j++) { result += Math.Abs(a[0 j] - a[0 0]); } return result; } static void Main(string[] args) { int[ ] a = { { 1 1 } { 1 1 } }; int[ ] b = { { 1 2 } { 3 4 } }; Console.WriteLine(countOperations(a b)); } }
// JavaScript program to find number of transformation // to make two Matrix Equal function countOperations(a b) { let n = a.length; let m = a[0].length; // Create difference matrix (a = a - b) for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { a[i][j] -= b[i][j]; } } // Check if transformation is possible using the // property a[i][j] - a[i][0] - a[0][j] + a[0][0] should // be 0 for (let i = 1; i < n; i++) { for (let j = 1; j < m; j++) { if (a[i][j] - a[i][0] - a[0][j] + a[0][0] !== 0) { return -1; } } } let result = 0; // Add operations needed for first column for (let i = 0; i < n; i++) { result += Math.abs(a[i][0]); } // Add operations needed for // first row (excluding a[0][0]) for (let j = 0; j < m; j++) { result += Math.abs(a[0][j] - a[0][0]); } return result; } //Driver code let a = [ [ 1 1 ] [ 1 1 ] ]; let b = [ [ 1 2 ] [ 3 4 ] ]; console.log(countOperations(a b));
Producción
3
Complejidad del tiempo: O(n*m)
Espacio Auxiliar: O(1)