Gitt to matriser a og b av størrelse n*m . Oppgaven er å finne det nødvendige antall transformasjonstrinn slik at begge matrisene blir like. Trykk -1 hvis dette ikke er mulig.
De transformasjon trinn er som følger:
- Velg en matrise av to matriser.
- Velg enten rad/kolonne av den valgte matrisen.
- Øk hvert element i valget rad/kolonne innen 1.
Eksempler:
Inndata:
a[][] = [[1 1]
[1 1]]b[][] = [[1 2]
[3 4]]Produksjon : 3
Forklaring :
[[1 1] -> [[1 2] -> [[1 2] -> [[1 2]
[1 1]] [1 2]] [2 3]] [3 4]]
Inndata :
a[][] = [[1 1]
[1 0]]b[][] = [[1 2]
[3 4]]hvor mange uker i en månedProduksjon : -1
Forklaring : Ingen transformasjon vil gjøre a og b like.
Nærme:
Tanken er det økende hvilken som helst rad/kolonne inn matrise a tilsvarer dekrementerende samme rad/kolonne inn matrise b .
Dette betyr at i stedet for å spore begge matrisene kan vi jobbe med forskjellen deres (a[i][j] - b[i][j]). Når vi øker en rad i ' en' alle elementene i den raden øker med 1 som er det samme som alle elementene i den raden i differansematrisen øker med 1. På samme måte når vi øker en kolonne i ' en' det tilsvarer å øke alle elementene i den kolonnen i differansematrisen med 1.
Dette lar oss transformere problemet til å jobbe med bare én matrise.
npm ren cache
Finn ut om det finnes en løsning eller ikke:
Etter å ha opprettet forskjellsmatrise for hver celle a[i][j] (unntatt første rad og første kolonne) sjekker vi om
a[i][j] - a[i][0] - a[0][j] + a[0][0] = 0.
Hvis denne ligningen ikke holder for noen celle, kan vi umiddelbart konkludere med at det ikke finnes noen løsning.
Hvorfor fungerer dette?
Tenk på hvordan rad og kolonne operasjoner påvirker hver celle: når vi utfører x operasjoner på rad jeg og og operasjoner på kolonne j a[i][j] endres med (x + y) a[i][0] endringer med x (bare radoperasjoner) a[0][j] endringer med y (bare kolonneoperasjoner) og a[0][0] påvirkes av verken rad i eller kolonne j operasjoner. Derfor (x + y) - x - y + 0 = 0 må holde for enhver gyldig løsning. Hvis denne ligningen ikke holder for noen celle, betyr det at ingen sekvens av rad- og kolonneoperasjoner kan transformere en matrise til en annen.
Beregn antall nødvendige transformasjoner:
C++For å beregne antall nødvendige transformasjoner trenger vi bare å se på første rad og første kolonne fordi:
- Vi oppsummerer først |a[i][0]| for all i (hvert første kolonneelement) fordi dette representerer hvor mange radoperasjoner vi trenger. For hver rad i trenger vi |a[i][0]| operasjoner for å gjøre det radelementet null.
- Så oppsummerer vi |a[0][j] - a[0][0]| for alle j (hvert første radelement minus første element) fordi dette representerer ytterligere kolonneoperasjoner som trengs. Vi trekker fra a[0][0] for å unngå å telle den to ganger siden radoperasjoner allerede har påvirket dette elementet.
- Summen av disse to gir oss minimum antall operasjoner nødvendig ettersom radoperasjoner håndterer de første kolonneforskjellene og kolonneoperasjoner håndterer de resterende forskjellene i den første raden.
// 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));
Produksjon
3
Tidskompleksitet: O(n*m)
Hjelpeplass: O(1)