Дадени две матрици а и b на размера n*m . Задачата е да се намери необходимото брой стъпки на трансформация така че двете матрици да станат равни. Печат -1 ако това не е възможно.
The трансформация стъпка е както следва:
- Изберете всяка една матрица от две матрици.
- Изберете едно от двете ред/колона на избраната матрица.
- Увеличете всеки елемент от избраното ред/колона от 1.
Примери:
вход:
a[][] = [[1 1]
[1 1]]b[][] = [[1 2]
[3 4]]Изход : 3
Обяснение :
[[1 1] -> [[1 2] -> [[1 2] -> [[1 2]
[1 1]] [1 2]] [2 3]] [3 4]]
Вход :
a[][] = [[1 1]
[1 0]]b[][] = [[1 2]
[3 4]]какво е java стекИзход : -1
Обяснение : Никаква трансформация няма да направи a и b равни.
Подход:
Идеята е, че нарастване произволен ред/колона матрица а е еквивалентно на намаляващ същия ред/колона в матрица b .
Това означава, че вместо да проследяваме и двете матрици, можем да работим с тяхната разлика (a[i][j] - b[i][j]). Когато увеличим ред в ' а' всички елементи в този ред се увеличават с 1, което е същото като всички елементи в този ред на матрицата на разликата, които се увеличават с 1. По същия начин, когато увеличаваме колона в ' а' това е еквивалентно на увеличаване на всички елементи в тази колона на матрицата на разликата с 1.
Това ни позволява да трансформираме проблема в работа само с една матрица.
лого на java
Определете дали съществува някакво решение или не:
След създаването на матрица на разликата за всяка клетка a[i][j] (с изключение на първия ред и първата колона) проверяваме дали
a[i][j] - a[i][0] - a[0][j] + a[0][0] = 0.
Ако това уравнение не е валидно за никоя клетка, можем веднага да заключим, че не съществува решение.
Защо това работи?
Помислете как ред и колона операции засягат всяка клетка: когато извършваме х операции върху ред аз и и операции на колона й a[i][j] промени с (x + y) a[i][0] промени с x (само операции с редове) a[0][j] промени с y (само операции с колони) и a[0][0] се влияе от нито ред i, нито колона j операции. Следователно (x + y) - x - y + 0 = 0 трябва да важи за всяко валидно решение. Ако това уравнение не важи за нито една клетка, това означава, че никоя последователност от операции с редове и колони не може да трансформира една матрица в друга.
Изчислете броя на необходимите трансформации:
C++За да изчислим броя на необходимите трансформации, трябва само да погледнем първи ред и първа колона защото:
- Първо обобщаваме |a[i][0]| за всички i (всеки първи елемент от колона), защото това представлява колко операции с ред са ни необходими. За всеки ред i се нуждаем от |a[i][0]| операции, за да направите този елемент на ред нула.
- След това обобщаваме |a[0][j] - a[0][0]| за всички j (всеки елемент от първия ред минус първия елемент), защото това представлява необходимите допълнителни операции с колони. Изваждаме a[0][0], за да избегнем преброяването му два пъти, тъй като операциите с ред вече са засегнали този елемент.
- Сумата от тези две ни дава минимален брой операции необходими, тъй като операциите с редове обработват разликите в първата колона, а операциите с колони обработват останалите разлики в първия ред.
// 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));
Изход
3
Времева сложност: O(n*m)
Помощно пространство: О(1)