Gegeben zwei Matrizen a Und B der Größe n*m . Die Aufgabe besteht darin, das Gesuchte zu finden Anzahl der Transformationsschritte sodass beide Matrizen gleich werden. Drucken -1 wenn dies nicht möglich ist.
Der Transformation Schritt ist wie folgt:
- Wählen Sie eine beliebige Matrix aus zwei Matrizen aus.
- Wählen Sie eines von beiden Zeile/Spalte der ausgewählten Matrix.
- Erhöhen Sie jedes Element der Auswahl Zeile/Spalte um 1.
Beispiele:
Eingang:
a[][] = [[1 1]
[1 1]]b[][] = [[1 2]
[3 4]]Ausgabe : 3
Erläuterung :
[[1 1] -> [[1 2] -> [[1 2] -> [[1 2]
[1 1]] [1 2]] [2 3]] [3 4]]
Eingang :
a[][] = [[1 1]
[1 0]]123Filmb[][] = [[1 2]
[3 4]]Ausgabe : -1
Erläuterung : Keine Transformation wird a und b gleich machen.
Ansatz:
Die Idee ist das inkrementieren jede Zeile/Spalte in Matrix a ist äquivalent zu dekrementieren die gleiche Zeile/Spalte in Matrix b .
Das bedeutet, dass wir, anstatt beide Matrizen zu verfolgen, mit ihren Unterschieden arbeiten können (a[i][j] - b[i][j]). Wenn wir eine Zeile in ' erhöhen A' Alle Elemente in dieser Zeile erhöhen sich um 1, was gleichbedeutend mit der Erhöhung aller Elemente in dieser Zeile der Differenzmatrix um 1 ist. Ähnlich verhält es sich, wenn wir eine Spalte in ' erhöhen. A' Dies entspricht der Erhöhung aller Elemente in dieser Spalte der Differenzmatrix um 1.
Dadurch können wir das Problem in die Arbeit mit nur einer Matrix umwandeln.
npm sauberer Cache
Stellen Sie fest, ob eine Lösung existiert oder nicht:
Nach dem Erstellen des Differenzmatrix für jede Zelle a[i][j] (mit Ausnahme der ersten Zeile und der ersten Spalte) prüfen wir, ob
a[i][j] - a[i][0] - a[0][j] + a[0][0] = 0.
Wenn diese Gleichung für keine Zelle gilt, können wir sofort schlussfolgern, dass keine Lösung existiert.
Warum funktioniert das?
Überlegen Sie, wie Zeile und Spalte Operationen wirken sich auf jede Zelle aus: wenn wir sie ausführen X Operationen auf Zeile ich Und Und Operationen an der Spalte J a[i][j] ändert sich um (x + y) a[i][0] ändert sich um x (nur Zeilenoperationen), a[0][j] ändert sich um y (nur Spaltenoperationen) und a[0][0] wird beeinflusst von weder Zeile i noch Spalte j Operationen. daher (x + y) - x - y + 0 = 0 muss für jede gültige Lösung gelten. Wenn diese Gleichung für keine Zelle gilt, bedeutet das, dass keine Folge von Zeilen- und Spaltenoperationen eine Matrix in eine andere umwandeln kann.
Berechnen Sie die Anzahl der erforderlichen Transformationen:
ipconfig für Ubuntu
C++Um die Anzahl der erforderlichen Transformationen zu berechnen, müssen wir uns nur die ansehen erste Reihe Und erste Spalte Weil:
- Wir fassen zunächst zusammen |a[i][0]| für alle i (jedes erste Spaltenelement), da dies angibt, wie viele Zeilenoperationen wir benötigen. Für jede Zeile i benötigen wir |a[i][0]| Operationen, um dieses Zeilenelement auf Null zu setzen.
- Dann fassen wir zusammen |a[0][j] - a[0][0]| für alle j (jedes erste Zeilenelement minus erstes Element), da dies zusätzliche erforderliche Spaltenoperationen darstellt. Wir subtrahieren a[0][0], um eine doppelte Zählung zu vermeiden, da sich Zeilenoperationen bereits auf dieses Element ausgewirkt haben.
- Die Summe dieser beiden ergibt das minimale Anzahl von Operationen erforderlich, da Zeilenoperationen die Unterschiede in der ersten Spalte und Spaltenoperationen die verbleibenden Unterschiede in der ersten Zeile verarbeiten.
// 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));
Ausgabe
3
Zeitkomplexität: O(n*m)
Hilfsraum: O(1)