İki tane verildi matrisler a Ve B boyutta n*m . Görev gerekli olanı bulmaktır dönüşüm adımlarının sayısı böylece her iki matris de eşit olur. Yazdır -1 eğer bu mümkün değilse.
dönüşüm adım şu şekildedir:
Java dizi listesi
- İki matristen herhangi birini seçin.
- İkisinden birini seçin satır/sütun seçilen matrisin
- Seçimin her öğesini artır satır/sütun 1'e kadar.
Örnekler:
Giriş:
a[][] = [[1 1]
[1 1]]b[][] = [[1 2]
[3 4]]Çıkış : 3
Açıklama :
[[1 1] -> [[1 2] -> [[1 2] -> [[1 2]
[1 1]] [1 2]] [2 3]] [3 4]]
Giriş :
a[][] = [[1 1]
[1 0]]b[][] = [[1 2]
[3 4]]Çıkış : -1
Açıklama : Hiçbir dönüşüm a ve b'yi eşitlemez.
Yaklaşmak:
Fikir şu ki artan herhangi bir satır/sütun matris a eşdeğerdir azalan aynı satır/sütun matris b .
Bu, her iki matrisi de takip etmek yerine farklarıyla çalışabileceğimiz anlamına gelir. (a[i][j] - b[i][j]). 'de bir satırı artırdığımızda A' o satırdaki tüm elemanlar 1 artar; bu, fark matrisinin o satırındaki tüm elemanların 1 artmasıyla aynıdır. Benzer şekilde, ' cinsinden bir sütunu arttırdığımızda A' fark matrisinin o sütunundaki tüm elemanları 1 artırmaya eşdeğerdir.
Bu, sorunu tek bir matrisle çalışmaya dönüştürmemize olanak tanır.
java logosu
Herhangi bir çözümün mevcut olup olmadığını belirleyin:
Oluşturduktan sonra fark matrisi her hücre için a[i][j] (ilk satır ve ilk sütun hariç) olup olmadığını kontrol ederiz
a[i][j] - a[i][0] - a[0][j] + a[0][0] = 0.
Eğer bu denklem herhangi bir hücre için geçerli değilse, hemen hiçbir çözümün olmadığı sonucuna varabiliriz.
Bu neden işe yarıyor?
Nasıl olduğunu düşün satır ve sütun işlemler her hücreyi etkiler: gerçekleştirdiğimizde X satırdaki işlemler Ben Ve Ve sütundaki işlemler J a[i][j] (x + y)'ye göre değişiklikler a[i][0] x'e göre değişiklikler (yalnızca satır işlemleri) a[0][j], y'ye göre değişir (yalnızca sütun işlemleri) ve a[0][0] şunlardan etkilenir: ne satır i ne de sütun j operasyonlar. Öyleyse (x + y) - x - y + 0 = 0 herhangi bir geçerli çözüm için geçerli olmalıdır. Bu denklem herhangi bir hücre için geçerli değilse, bu, hiçbir satır ve sütun işlemi dizisinin bir matrisi diğerine dönüştüremeyeceği anlamına gelir.
Gerekli dönüşüm sayısını hesaplayın:
C++Gerekli dönüşüm sayısını hesaplamak için yalnızca şuna bakmamız gerekir: ilk sıra Ve ilk sütun Çünkü:
- İlk önce özetliyoruz |a[i][0]| tüm i için (her bir ilk sütun öğesi) çünkü bu, kaç tane satır işlemine ihtiyacımız olduğunu temsil eder. Her satır için |a[i][0]|'ye ihtiyacımız var. bu satır öğesini sıfır yapmak için yapılan işlemler.
- Sonra özetliyoruz |a[0][j] - a[0][0]| tüm j için (her ilk satır öğesi eksi ilk öğe) çünkü bu, gereken ek sütun işlemlerini temsil eder. Satır işlemleri bu öğeyi zaten etkilediğinden, iki kez saymayı önlemek için a[0][0]'ı çıkarırız.
- Bu ikisinin toplamı bize şunu verir: minimum işlem sayısı Satır işlemleri ilk sütun farklılıklarını ele aldığından ve sütun işlemleri ilk satırda kalan farkları ele aldığından bu işlem gereklidir.
// 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));
Çıkış
3
Zaman Karmaşıklığı: Ç(n*m)
Yardımcı Alan: Ç(1)