Étant donné deux matrices un et b de taille n*m . La tâche est de trouver le nécessaire nombre d'étapes de transformation de sorte que les deux matrices deviennent égales. Imprimer -1 si cela n'est pas possible.
Le transformation l'étape est la suivante :
- Sélectionnez une matrice parmi deux matrices.
- Choisissez soit ligne/colonne de la matrice sélectionnée.
- Incrémentez chaque élément de la sélection ligne/colonne par 1.
Exemples :
Saisir:
une[][] = [[1 1]
[1 1]]b[][] = [[1 2]
[3 4]]Sortir : 3
Explication :
[[1 1] -> [[1 2] -> [[1 2] -> [[1 2]
[1 1]] [1 2]] [2 3]] [3 4]]
Saisir :
une[][] = [[1 1]
[1 0]]b[][] = [[1 2]
[3 4]]Sortir : -1
Explication : Aucune transformation ne rendra a et b égaux.
Approche:
L'idée est que incrémentation n'importe quelle ligne/colonne dans matrice une est équivalent à décrémentation la même ligne/colonne dans matrice b .
Cela signifie qu'au lieu de suivre les deux matrices, nous pouvons travailler avec leurs différences. (a[i][j] - b[i][j]). Quand on incrémente une ligne dans ' un' tous les éléments de cette ligne augmentent de 1, ce qui équivaut à tous les éléments de cette ligne de la matrice de différence augmentant de 1. De même, lorsque nous incrémentons une colonne dans ' un' cela équivaut à augmenter de 1 tous les éléments de cette colonne de la matrice de différence.
pseudo seulementCela nous permet de transformer le problème en travaillant avec une seule matrice.
Déterminez si une solution existe ou non :
Après avoir créé le matrice de différence pour chaque cellule une[i][j] (hors première ligne et première colonne) on vérifie si
a[i][j] - a[i][0] - a[0][j] + a[0][0] = 0.
Si cette équation ne s’applique à aucune cellule, nous pouvons immédiatement conclure qu’aucune solution n’existe.
Pourquoi est-ce que ça marche ?
Pensez à la façon dont ligne et colonne les opérations affectent chaque cellule : lorsque nous effectuons x opérations sur la ligne je et et opérations sur la colonne j une[i][j] change de (x + y) une[i][0] change par x (opérations sur les lignes uniquement) a[0][j] change par y (opérations sur les colonnes uniquement) et a[0][0] est affecté par ni la ligne i ni la colonne j opérations. Donc (x + y) - x - y + 0 = 0 doit être valable pour toute solution valable. Si cette équation ne s'applique à aucune cellule, cela signifie qu'aucune séquence d'opérations sur les lignes et les colonnes ne peut transformer une matrice en une autre.
Calculez le nombre de transformations requises :
C++Pour calculer le nombre de transformations nécessaires, il suffit de regarder le première rangée et première colonne parce que:
- Nous résumons d'abord |une[i][0]| pour tout i (chaque premier élément de colonne) car cela représente le nombre d'opérations de ligne dont nous avons besoin. Pour chaque ligne i nous avons besoin de |a[i][0]| opérations pour rendre cet élément de ligne nul.
- Ensuite, nous résumons |a[0][j] - a[0][0]| pour tous les j (chaque élément de la première ligne moins le premier élément), car cela représente des opérations de colonne supplémentaires nécessaires. Nous soustrayons a[0][0] pour éviter de le compter deux fois puisque les opérations sur les lignes ont déjà affecté cet élément.
- La somme de ces deux nous donne nombre minimum d'opérations nécessaire car les opérations sur les lignes gèrent les différences de la première colonne et les opérations sur les colonnes gèrent les différences restantes dans la première ligne.
// 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));
Sortir
3
Complexité temporelle : O(n*m)
Espace auxiliaire : O(1)