Biorąc pod uwagę dwa macierze a I B wielkościowy n*m . Zadanie polega na znalezieniu potrzebnego liczba kroków transformacji tak aby obie macierze stały się równe. Wydrukować -1 jeśli nie jest to możliwe.
The transformacja krok jest następujący:
- Wybierz dowolną macierz z dwóch macierzy.
- Wybierz albo wiersz/kolumna wybranej matrycy.
- Zwiększ każdy element zaznaczenia wiersz/kolumna o 1.
Przykłady:
Wejście:
a[][] = [[1 1]
[1 1]]b[][] = [[1 2]
[3 4]]Wyjście : 3
Wyjaśnienie :
[[1 1] -> [[1 2] -> [[1 2] -> [[1 2]
[1 1]] [1 2]] [2 3]] [3 4]]
Wejście :
a[][] = [[1 1]
[1 0]]b[][] = [[1 2]
[3 4]]Wyjście : -1
Wyjaśnienie : Żadna transformacja nie sprawi, że a i b będą równe.
Zbliżać się:
Pomysł jest taki inkrementacja dowolny wiersz/kolumna w macierz a jest równoważne malejące w tym samym wierszu/kolumnie matryca b .
Oznacza to, że zamiast śledzić obie macierze, możemy pracować z ich różnicą (a[i] [j] - b[i] [j]). Kiedy zwiększamy wiersz w ' A' wszystkie elementy w tym wierszu zwiększają się o 1, co jest takie samo, jak wszystkie elementy w tym wierszu macierzy różnic zwiększając się o 1. Podobnie, gdy zwiększamy kolumnę w ' A' jest to równoważne zwiększeniu wszystkich elementów w tej kolumnie macierzy różnic o 1.
Java, spróbuj złapaćDzięki temu możemy przekształcić problem w pracę z tylko jedną matrycą.
Ustal, czy istnieje jakieś rozwiązanie, czy nie:
Po utworzeniu macierz różnic dla każdej komórki a[i] (z wyłączeniem pierwszego wiersza i pierwszej kolumny) sprawdzamy, czy
a[i] [j] - a[i] [0] - a[0] [j] + a[0] [0] = 0.
Jeśli to równanie nie dotyczy żadnej komórki, możemy od razu stwierdzić, że rozwiązanie nie istnieje.
Dlaczego to działa?
Pomyśl jak wiersz i kolumna operacje wpływają na każdą komórkę: kiedy wykonujemy X operacje na wierszu I I I operacje na kolumnie J a[i] zmienia się o (x + y) a[i] [0] zmiany o x (tylko operacje na wierszach) a[0][j] zmiany o y (tylko operacje na kolumnach) i a[0][0] wpływa ani wiersz i, ani kolumna j operacje. Dlatego (x + y) - x - y + 0 = 0 musi obowiązywać dla każdego prawidłowego rozwiązania. Jeśli to równanie nie dotyczy żadnej komórki, oznacza to, że żadna sekwencja operacji na wierszach i kolumnach nie może przekształcić jednej macierzy w drugą.
Oblicz liczbę wymaganych przekształceń:
C++Aby obliczyć liczbę wymaganych przekształceń, wystarczy spojrzeć na pierwszy rząd I pierwsza kolumna ponieważ:
- Najpierw podsumowujemy |a[i][0]| dla wszystkich i (każdego elementu pierwszej kolumny), ponieważ reprezentuje to liczbę potrzebnych operacji na wierszach. Dla każdego wiersza i potrzebujemy |a[i][0]| operacje, aby element wiersza był zerowy.
- Następnie podsumowujemy |a[0][j] - a[0][0]| dla wszystkich j (każdy element pierwszego wiersza minus pierwszy element), ponieważ reprezentuje to potrzebne dodatkowe operacje na kolumnach. Odejmujemy a[0][0], aby uniknąć dwukrotnego liczenia, ponieważ operacje na wierszach wpłynęły już na ten element.
- Suma tych dwóch daje nam minimalna liczba operacji potrzebne, ponieważ operacje na wierszach obsługują różnice w pierwszej kolumnie, a operacje na kolumnach obsługują pozostałe różnice w pierwszym wierszu.
// 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));
Wyjście
3
Złożoność czasowa: O(n*m)
Przestrzeń pomocnicza: O(1)