Doti divi matricas a un b izmēra n*m . Uzdevums ir atrast vajadzīgo transformācijas soļu skaits lai abas matricas kļūtu vienādas. Drukāt -1 ja tas nav iespējams.
The transformācija solis ir šāds:
- Izvēlieties jebkuru no divām matricām.
- Izvēlieties kādu no rinda/kolonna no atlasītās matricas.
- Palieliniet katru atlases elementu rinda/kolonna ar 1.
Piemēri:
Ievade:
a[][] = [[1 1]
[11]]b[][] = [[1 2]
[3 4]]Izvade : 3
Paskaidrojums :
[[1 1] -> [[1 2] -> [[1 2] -> [[1 2]
[1 1]] [1 2]] [2 3]] [3 4]]
Ievade :
a[][] = [[1 1]
[10]]b[][] = [[1 2]
[3 4]]Izvade : -1
Paskaidrojums : Neviena transformācija nepadarīs a un b vienādu.
Pieeja:
Ideja ir tāda pieaugot jebkura rinda/kolonna matrica a ir līdzvērtīgs samazinās tajā pašā rindā/kolonā matrica b .
Tas nozīmē, ka tā vietā, lai izsekotu abas matricas, mēs varam strādāt ar to atšķirību (a[i][j] - b[i][j]). Kad mēs palielinām rindu a' visi elementi šajā rindā palielinās par 1, kas ir tāds pats kā visi elementi šajā starpības matricas rindā, kas palielinās par 1. Līdzīgi, kad mēs palielinām kolonnu a' tas ir līdzvērtīgs visu elementu palielināšanai šajā starpības matricas kolonnā par 1.
Tas ļauj mums pārvērst problēmu darbā tikai ar vienu matricu.
Nosakiet, vai risinājums pastāv vai nē:
Pēc izveidošanas atšķirību matrica katrai šūnai a[i][j] (izņemot pirmo rindu un pirmo kolonnu) pārbaudām, vai
a[i][j] - a[i][0] - a[0][j] + a[0][0] = 0.
Ja šis vienādojums nav spēkā nevienai šūnai, mēs varam uzreiz secināt, ka risinājums nepastāv.
Kāpēc tas darbojas?
Padomājiet, kā rinda un kolonna operācijas ietekmē katru šūnu: kad mēs veicam x operācijas rindā i un un operācijas kolonnā j a[i][j] izmaiņas par (x + y) a[i][0] izmaiņas par x (tikai rindu darbībām) a[0][j] izmaiņas par y (tikai kolonnu operācijām) un a[0][0] ietekmē ne i rinda, ne j kolonna operācijas. Tāpēc (x + y) - x - y + 0 = 0 ir jātur spēkā jebkuram derīgam risinājumam. Ja šis vienādojums nav spēkā nevienai šūnai, tas nozīmē, ka neviena rindu un kolonnu darbību secība nevar pārveidot vienu matricu citā.
Aprēķiniet nepieciešamo transformāciju skaitu:
C++Lai aprēķinātu nepieciešamo transformāciju skaitu, mums tikai jāaplūko pirmā rinda un pirmā kolonna jo:
- Mēs vispirms apkopojam |a[i][0]| visiem i (katram pirmās kolonnas elementam), jo tas norāda, cik rindas operāciju mums ir nepieciešams. Katrai i rindai mums ir nepieciešams |a[i][0]| darbības, lai padarītu šo rindas elementu par nulli.
- Tad mēs apkopojam |a[0][j] - a[0][0]| visiem j (katrs pirmās rindas elements mīnus pirmais elements), jo tas apzīmē nepieciešamās papildu kolonnas darbības. Mēs atņemam a[0][0], lai tas netiktu skaitīts divreiz, jo rindu darbības jau ir ietekmējušas šo elementu.
- Šo divu summu summa dod mums minimālais operāciju skaits nepieciešams, jo rindu darbības apstrādā pirmās kolonnas atšķirības un kolonnu darbības apstrādā atlikušās atšķirības pirmajā rindā.
// 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));
Izvade
3
Laika sarežģītība: O(n*m)
Palīgtelpa: O(1)