Donats dos matrius a i b de mida n*m . La tasca és trobar el necessari nombre de passos de transformació de manera que ambdues matrius es tornen iguals. Imprimeix -1 si això no és possible.
El transformació el pas és el següent:
- Seleccioneu una matriu qualsevol d'entre dues.
- Trieu qualsevol fila/columna de la matriu seleccionada.
- Incrementa cada element de la selecció fila/columna per 1.
Exemples:
Entrada:
a[][] = [[1 1]
[1 1]]b[][] = [[1 2]
[3 4]]Sortida : 3
Explicació :
[[1 1] -> [[1 2] -> [[1 2] -> [[1 2]
[1 1]] [1 2]] [2 3]] [3 4]]
Entrada :
a[][] = [[1 1]
[1 0]]b[][] = [[1 2]
[3 4]]Sortida : -1
Explicació : Cap transformació farà que a i b siguin iguals.
Enfocament:
La idea és que augmentant qualsevol fila/columna matriu a és equivalent a decreixent la mateixa fila/columna matriu b .
Això vol dir que en comptes de fer el seguiment de les dues matrius podem treballar amb la seva diferència (a[i][j] - b[i][j]). Quan incrementem una fila en ' a' tots els elements d'aquesta fila augmenten en 1, que és el mateix que tots els elements d'aquesta fila de la matriu de diferències que augmenten en 1. De la mateixa manera, quan incrementem una columna en ' a' és equivalent a augmentar en 1 tots els elements d'aquesta columna de la matriu de diferències.
Això ens permet transformar el problema en treballar amb una sola matriu.
Determineu si existeix alguna solució o no:
Després de crear el matriu de diferències per a cada cèl·lula a[i][j] (excloent la primera fila i la primera columna) comprovem si
a[i][j] - a[i][0] - a[0][j] + a[0][0] = 0.
Si aquesta equació no es compleix per a cap cel·la, podem concloure immediatament que no existeix cap solució.
Per què funciona això?
Pensa com fila i columna les operacions afecten a cada cèl·lula: quan realitzem x operacions en fila i i i operacions a la columna j a[i][j] canvia en (x + y) a[i][0] canvia per x (només operacions de fila) a[0][j] canvia per y (només operacions de columna) i a[0][0] es veu afectada per ni la fila i ni la columna j operacions. Per tant (x + y) - x - y + 0 = 0 ha de mantenir-se per a qualsevol solució vàlida. Si aquesta equació no s'aplica a cap cel·la, vol dir que cap seqüència d'operacions de fila i columna pot transformar una matriu en una altra.
Calcula el nombre de transformacions necessàries:
C++Per calcular el nombre de transformacions necessàries només hem de mirar el primera fila i primera columna perquè:
- Primer resumim |a[i][0]| per a tot i (cada element de la primera columna) perquè això representa quantes operacions de fila necessitem. Per a cada fila i necessitem |a[i][0]| operacions per fer que l'element de fila sigui zero.
- Aleshores resumim |a[0][j] - a[0][0]| per a tots els j (cada element de la primera fila menys el primer element) perquè això representa operacions de columna addicionals necessàries. Restem a[0][0] per evitar comptar-lo dues vegades ja que les operacions de fila ja han afectat aquest element.
- La suma d'aquests dos ens dóna el nombre mínim d'operacions necessàries ja que les operacions de fila gestionen les diferències de la primera columna i les operacions de columna gestionen les diferències restants a 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));
Sortida
3
Complexitat temporal: O(n*m)
Espai auxiliar: O(1)