Givet to matricer a og b af størrelse n*m . Opgaven er at finde det ønskede antal transformationstrin så begge matricer bliver lige store. Trykke -1 hvis dette ikke er muligt.
De transformation trin er som følger:
- Vælg en hvilken som helst matrix ud af to matricer.
- Vælg enten række/kolonne af den valgte matrix.
- Forøg hvert element i valget række/kolonne inden 1.
Eksempler:
Input:
a[][] = [[1 1]
[1 1]]b[][] = [[1 2]
[3 4]]Produktion : 3
Forklaring :
[[1 1] -> [[1 2] -> [[1 2] -> [[1 2]
[1 1]] [1 2]] [2 3]] [3 4]]
Input :
a[][] = [[1 1]
[1 0]]b[][] = [[1 2]
[3 4]]hvor mange uger på en månedProduktion : -1
Forklaring : Ingen transformation vil gøre a og b ens.
Nærme sig:
Tanken er det stigende enhver række/kolonne ind matrix a svarer til dekrementerende samme række/kolonne ind matrix b .
Det betyder, at vi i stedet for at spore begge matricer kan arbejde med deres forskel (a[i][j] - b[i][j]). Når vi øger en række i ' en' alle elementer i den række stiger med 1, hvilket er det samme, som alle elementer i denne række i differensmatricen øges med 1. På samme måde, når vi øger en kolonne i ' en' det svarer til at øge alle elementer i den kolonne i differensmatricen med 1.
Dette giver os mulighed for at transformere problemet til kun at arbejde med én matrix.
npm rense cache
Bestem, om der findes en løsning eller ej:
Efter at have oprettet forskelsmatrix for hver celle a[i][j] (eksklusive første række og første kolonne) tjekker vi om
a[i][j] - a[i][0] - a[0][j] + a[0][0] = 0.
Hvis denne ligning ikke holder for nogen celle, kan vi straks konkludere, at der ikke findes nogen løsning.
Hvorfor virker dette?
Tænk over hvordan række og kolonne operationer påvirker hver celle: når vi udfører x operationer på række jeg og og operationer på kolonne j a[i][j] ændres med (x + y) a[i][0] ændringer med x (kun rækkeoperationer) a[0][j] ændringer med y (kun kolonneoperationer) og a[0][0] er påvirket af hverken række i eller kolonne j operationer. Derfor (x + y) - x - y + 0 = 0 skal holde for enhver gyldig løsning. Hvis denne ligning ikke holder for nogen celle, betyder det, at ingen sekvens af række- og kolonneoperationer kan transformere en matrix til en anden.
Beregn antallet af nødvendige transformationer:
C++For at beregne antallet af nødvendige transformationer behøver vi kun at se på første række og første kolonne fordi:
- Vi opsummerer først |a[i][0]| for alle i (hvert første kolonneelement), fordi dette repræsenterer, hvor mange rækkeoperationer vi har brug for. For hver række i skal vi bruge |a[i][0]| operationer for at gøre dette rækkeelement til nul.
- Så opsummerer vi |a[0][j] - a[0][0]| for alle j (hvert element i første række minus første element), fordi dette repræsenterer yderligere nødvendige kolonneoperationer. Vi trækker a[0][0] fra for at undgå at tælle det to gange, da rækkeoperationer allerede har påvirket dette element.
- Summen af disse to giver os minimum antal operationer nødvendig, da rækkeoperationer håndterer de første kolonneforskelle, og kolonneoperationer håndterer de resterende forskelle i den første række.
// 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));
Produktion
3
Tidskompleksitet: O(n*m)
Hjælpeplads: O(1)