نظرا لاثنين المصفوفات أ و ب من الحجم ن * م . المهمة هي العثور على المطلوب عدد خطوات التحويل بحيث تصبح المصفوفتان متساويتين. مطبعة -1 إذا كان هذا غير ممكن.
ال تحويل الخطوة هي كما يلي:
- حدد أي مصفوفة واحدة من بين مصفوفتين.
- اختر إما الصف / العمود للمصفوفة المختارة
- قم بزيادة كل عنصر من عناصر التحديد الصف / العمود بواسطة 1.
أمثلة:
مدخل:
أ[][] = [[1 1]
[1 1]]ب[][] = [[1 2]
[3 4]]الإخراج : 3
توضيح :
[[1 1] -> [[1 2] -> [[1 2] -> [[1 2]
[1 1]] [1 2]] [2 3]] [3 4]]
مدخل :
أ[][] = [[1 1]
[1 0]]ب[][] = [[1 2]
[3 4]]الإخراج : -1
توضيح : لا يوجد تحويل سيجعل a وb متساويين.
يقترب:
الفكرة هي أن متزايد أي صف/عمود في مصفوفة أ يعادل التناقص نفس الصف/العمود في مصفوفة ب .
هذا يعني أنه بدلًا من تتبع المصفوفتين، يمكننا التعامل مع الفرق بينهما (أ[i] [ي] - ب [i] [ي]). عندما نقوم بزيادة صف في ' أ' جميع العناصر في هذا الصف تزيد بمقدار 1 وهو نفس كل العناصر الموجودة في هذا الصف من مصفوفة الفرق التي تزيد بمقدار 1. وبالمثل عندما نزيد عمودًا في " أ' إنه يعادل زيادة جميع العناصر الموجودة في هذا العمود من مصفوفة الفرق بمقدار 1.
وهذا يسمح لنا بتحويل المشكلة إلى العمل بمصفوفة واحدة فقط.
تحديد ما إذا كان هناك أي حل موجود أم لا:
بعد إنشاء مصفوفة الفرق لكل خلية أ[ط] [ي] (باستثناء الصف الأول والعمود الأول) نتحقق مما إذا كان
a[i][j] - a[i][0] - a[0][j] + a[0][0] = 0.
إذا كانت هذه المعادلة لا تنطبق على أي خلية يمكننا أن نستنتج على الفور أنه لا يوجد حل.
لماذا يعمل هذا؟
فكر في كيفية ذلك الصف والعمود تؤثر العمليات على كل خلية: عندما نؤديها س العمليات على التوالي أنا و و العمليات على العمود ي أ[ط] [ي] التغييرات بواسطة (س + ص) أ[i][0] التغييرات بواسطة x (عمليات الصفوف فقط) تتغير a[0][j] بواسطة y (عمليات الأعمدة فقط) ويتأثر a[0][0] بـ لا الصف i ولا العمود j العمليات. لذلك (س + ص) - س - ص + 0 = 0 يجب أن تعقد لأي حل صالح. إذا لم تنطبق هذه المعادلة على أي خلية، فهذا يعني أنه لا يمكن لتسلسل عمليات الصف والعمود تحويل مصفوفة إلى أخرى.
حساب عدد التحولات المطلوبة:
C++لحساب عدد التحولات المطلوبة نحتاج فقط إلى إلقاء نظرة على الصف الأول و العمود الأول لأن:
- نحن نلخص أولا |a[i][0]| لكل i (كل عنصر في العمود الأول) لأن هذا يمثل عدد عمليات الصف التي نحتاجها. لكل صف نحتاج |a[i][0]| عمليات لجعل عنصر الصف هذا صفرًا.
- ثم نلخص |a[0][j] - أ[0][0]| لجميع j (كل عنصر في الصف الأول ناقص العنصر الأول) لأن هذا يمثل عمليات العمود الإضافية المطلوبة. نحن نطرح [0] [0] لتجنب حسابه مرتين لأن عمليات الصف قد أثرت بالفعل على هذا العنصر.
- مجموع هذين يعطينا الحد الأدنى لعدد العمليات مطلوب حيث تتعامل عمليات الصف مع اختلافات العمود الأول وتتعامل عمليات العمود مع الاختلافات المتبقية في الصف الأول.
// C++ program to find number of transformation // to make two Matrix Equal #include using namespace std; int countOperations(vector<vector<int>> &a vector<vector<int>> &b) { int n = a.size(); int m = a[0].size(); // 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 += abs(a[i][0]); } // Add operations needed for // first row (excluding a[0][0]) for (int j = 0; j < m; j++) { result += abs(a[0][j] - a[0][0]); } return result; } int main() { vector<vector<int>> a = {{1 1} {1 1}}; vector<vector<int>> b = {{1 2} {3 4}}; cout << countOperations(a b); return 0; }
Java // 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 # 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# // 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 // 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
تعقيد الوقت: يا (ن * م)
المساحة المساعدة: يا(1)