Dato due matrici a E B di dimensione n*m . Il compito è trovare quello richiesto numero di passaggi di trasformazione in modo che entrambe le matrici diventino uguali. Stampa -1 se questo non è possibile.
IL trasformazione il passo è il seguente:
- Seleziona una matrice qualsiasi tra due matrici.
- Scegli uno dei due riga/colonna della matrice selezionata.
- Incrementa ogni elemento della selezione riga/colonna entro 1.
Esempi:
Ingresso:
un[][] = [[1 1]
[1 1]]b[][] = [[1 2]
[3 4]]Produzione : 3
Spiegazione :
[[1 1] -> [[1 2] -> [[1 2] -> [[1 2]
[1 1]] [1 2]] [2 3]] [3 4]]
Ingresso :
un[][] = [[1 1]
[1 0]]b[][] = [[1 2]
[3 4]]oggetto di JavaProduzione : -1
Spiegazione : Nessuna trasformazione renderà a e b uguali.
Approccio:
L'idea è questa incrementale qualsiasi riga/colonna in matrice a è equivalente a decrescente la stessa riga/colonna matrice b .
Ciò significa che invece di tracciare entrambe le matrici possiamo lavorare con la loro differenza (a[i][j] - b[i][j]). Quando incrementiamo una riga in ' UN' tutti gli elementi in quella riga aumentano di 1 che è uguale a tutti gli elementi in quella riga della matrice differenza aumentano di 1. Allo stesso modo quando incrementiamo una colonna in ' UN' equivale ad aumentare di 1 tutti gli elementi in quella colonna della matrice delle differenze.
Questo ci permette di trasformare il problema nel lavorare con una sola matrice.
formato stringa java
Determina se esiste una soluzione o meno:
Dopo aver creato il matrice differenza per ogni cella un[i][j] (esclusa la prima riga e la prima colonna) controlliamo se
a[i] [j] - a[i] [0] - a[0] [j] + a[0] [0] = 0.
Se questa equazione non vale per nessuna cella possiamo concludere immediatamente che non esiste alcuna soluzione.
Perché funziona?
Pensa a come riga e colonna le operazioni influenzano ogni cella: quando eseguiamo X operazioni sulla riga io E E operazioni sulla colonna J un[i][j] cambia di (x + y) un[i][0] cambia di x (solo operazioni su righe) a[0][j] cambia di y (solo operazioni su colonne) e a[0][0] è influenzato da né la riga i né la colonna j operazioni. Perciò (x + y) - x - y + 0 = 0 deve valere per qualsiasi soluzione valida. Se questa equazione non vale per nessuna cella significa che nessuna sequenza di operazioni su righe e colonne può trasformare una matrice in un'altra.
Calcolare il numero di trasformazioni richieste:
C++Per calcolare il numero di trasformazioni richieste dobbiamo solo guardare il file prima fila E prima colonna Perché:
- Per prima cosa riassumiamo |a[i][0]| per tutti i (ogni primo elemento di colonna) perché questo rappresenta quante operazioni di riga abbiamo bisogno. Per ogni riga i abbiamo bisogno di |a[i][0]| operazioni per rendere zero l'elemento di riga.
- Poi tiriamo le somme |a[0][j] - a[0][0]| per tutti i j (ogni primo elemento della riga meno il primo elemento) perché ciò rappresenta operazioni aggiuntive sulla colonna necessarie. Sottraiamo a[0][0] per evitare di contarlo due volte poiché le operazioni sulle righe hanno già interessato questo elemento.
- La somma di questi due ci dà il numero minimo di operazioni necessario poiché le operazioni sulle righe gestiscono le differenze della prima colonna e le operazioni sulle colonne gestiscono le differenze rimanenti nella prima riga.
// 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));
Produzione
3
Complessità temporale: O(n*m)
Spazio ausiliario: O(1)