Adott kettő mátrixok a és b méretű n*m . A feladat a szükséges megtalálása transzformációs lépések száma hogy mindkét mátrix egyenlő legyen. Nyomtatás -1 ha ez nem lehetséges.
A átalakítás lépés a következő:
- Válasszon ki egy mátrixot a két mátrix közül.
- Válasszon bármelyiket sor/oszlop a kiválasztott mátrixból.
- Növelje a kijelölés minden elemét sor/oszlop által 1.
Példák:
nevezd meg a várost az USA-ban
Bemenet:
a[][] = [[1 1]
[11]]b[][] = [[1 2]
[34]]Kimenet : 3
Magyarázat :
[[1 1] -> [[1 2] -> [[1 2] -> [[1 2]
[1 1]] [1 2]] [2 3]] [3 4]]
Bemenet :
a[][] = [[1 1]
[10]]b[][] = [[1 2]
[34]]Kimenet : -1
Magyarázat : Egyetlen transzformáció sem teszi egyenlővé a-t és b-t.
Megközelítés:
Az ötlet az növekvő bármely sor/oszlop be mátrix a egyenértékű csökkenő ugyanaz a sor/oszlop mátrix b .
Ez azt jelenti, hogy mindkét mátrix követése helyett a különbségükkel dolgozhatunk (a[i][j] - b[i][j]). Amikor egy sort növelünk a ' a' abban a sorban minden elem növekszik 1-gyel, ami megegyezik a különbségi mátrix adott sorának összes elemével, amely 1-gyel nő. Hasonlóképpen, ha növeljük a ' oszlopot a' ez egyenértékű a különbségi mátrix oszlopában lévő összes elem 1-gyel történő növelésével.
Ez lehetővé teszi számunkra, hogy a problémát egyetlen mátrixszal dolgozzuk át.
java logó
Határozza meg, hogy létezik-e megoldás vagy sem:
Miután létrehozta a különbségi mátrix minden egyes cellához a[i][j] (kivéve az első sort és az első oszlopot) ellenőrizzük, ha
a[i][j] - a[i][0] - a[0][j] + a[0][0] = 0.
Ha ez az egyenlet egyik cellára sem áll fenn, azonnal arra a következtetésre juthatunk, hogy nem létezik megoldás.
Miért működik ez?
Gondold végig, hogyan sor és oszlop műveletek az egyes cellákat érintik: amikor végrehajtjuk x műveletek a sorban én és és műveletek az oszlopon j a[i][j] változik (x + y) a[i][0] x-szel változik (csak sorműveletek) a[0][j] változása y-vel (csak oszlopműveletek) és az a[0][0]-t befolyásolja sem i sor, sem j oszlop műveleteket. Ezért (x + y) - x - y + 0 = 0 minden érvényes megoldáshoz érvényesnek kell lennie. Ha ez az egyenlet egyetlen cellára sem érvényes, az azt jelenti, hogy a sor- és oszlopműveletek egyetlen sorozata sem képes átalakítani egyik mátrixot egy másikba.
Számítsa ki a szükséges átalakítások számát:
tömblista rendezése
C++A szükséges transzformációk számának kiszámításához csak meg kell néznünk a első sor és első oszlop mert:
- Először összefoglaljuk |a[i][0]| minden i-re (minden első oszlopelemre), mert ez azt jelenti, hogy hány sorműveletre van szükségünk. Minden i sorhoz szükségünk van |a[i][0]| műveleteket a sorelem nullává tételéhez.
- Aztán összegezzük |a[0][j] - a[0][0]| minden j-re (minden első sor elem mínusz első elem), mert ez további oszlopműveleteket jelent. Kivonjuk az a[0][0]-t, hogy ne számoljuk kétszer, mivel a sorműveletek már érintették ezt az elemet.
- E kettő összege adja nekünk a minimális műveletek száma szükséges, mivel a sorműveletek kezelik az első oszlop különbségeit, az oszlopműveletek pedig az első sorban lévő többi különbséget.
// 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));
Kimenet
3
Időbeli összetettség: O(n*m)
Kiegészítő tér: O(1)