Дано два матриці a і b розміру н*м . Завдання знайти потрібне кількість кроків трансформації щоб обидві матриці стали рівними. Роздрукувати -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]]hashmap в 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.
Якщо це рівняння не виконується для жодної клітинки, ми можемо відразу зробити висновок, що розв’язку не існує.
Чому це працює?
Подумайте, як рядок і стовпець операції впливають на кожну клітинку: коли ми виконуємо x операції над рядком i і і операції на колонці j 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 (кожен перший елемент рядка мінус перший елемент), тому що це представляє необхідні додаткові операції зі стовпцями. Ми віднімаємо [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)