查找使兩個矩陣相等的變換數 · GeeksForGeeks 中文系列教程

# 查找使兩個矩陣相等的變換數 > 原文： [https://www.geeksforgeeks.org/find-number-transformation-make-two-matrix-equal/](https://www.geeksforgeeks.org/find-number-transformation-make-two-matrix-equal/) 給定 n * m 階的兩個矩陣 A 和 B。任務是找到所需的轉換步驟數，以使兩個矩陣都相等，如果不可能，則打印-1。轉換步驟如下： i）從兩個矩陣中選擇任意一個矩陣。 ii）選擇所選矩陣的行/列。 iii）將所選行/列的每個元素加 1。 **示例**： ``` Input : A[2][2]: 1 1 1 1 B[2][2]: 1 2 3 4 Output : 3 Explanation : 1 1 -> 1 2 -> 1 2 -> 1 2 1 1 -> 1 2 -> 2 3 -> 3 4 Input : A[2][2]: 1 1 1 0 B[2][2]: 1 2 3 4 Output : -1 Explanation : No transformation will make A and B equal. ``` 解決此問題的關鍵步驟是： **->** 將 A [] []的任何行遞增與將 B [] []的同一行遞減相同。因此，在僅對一個矩陣遞增或遞減轉換之后，我們便可以得到解決方案。 ``` So make A[i][j] = A[i][j] - B[i][j]. For example, If given matrices are, A[2][2] : 1 1 1 1 B[2][2] : 1 2 3 4 After subtraction, A[][] becomes, A[2][2] : 0 -1 -2 -3 ``` **->** 對于每個轉換，第一行/第一列元素都必須更改，其他第 i 行/列也是如此。 **->** 如果（A [i] [j] – A [i] [0] – A [0] [j] + A [0] [0]！= 0），那么無解存在。 **->** 第 1 行和第 1 列的元素僅導致結果。 ``` // Update matrix A[][] // so that only A[][] // has to be transformed for (i = 0; i < n; i++) for (j = 0; j < m; j++) A[i][j] -= B[i][j]; // Check necessary condition // For condition for // existence of full transformation for (i = 1; i < n; i++) for (j = 1; j < m; j++) if (A[i][j] - A[i][0] - A[0][j] + A[0][0] != 0) return -1; // If transformation is possible // calculate total transformation result = 0; for (i = 0; i < n; i++) result += abs(A[i][0]) for (j = 0; j < m; j++) result += abs(A[0][j] - A[0][0]); return abs(result); ``` ## [Recommended: Please try your approach on ***{IDE}*** first, before moving on to the solution.](https://ide.geeksforgeeks.org/) ## C++ ```cpp // C++ program to find // number of countOpsation // to make two matrix equals #include <bits/stdc++.h> using namespace std; const int MAX = 1000; int countOps(int A[][MAX], int B[][MAX],? ?????????????int m, int n) { ????// Update matrix A[][] ????// so that only A[][] ????// has to be countOpsed ????for (int i = 0; i < n; i++) ????????for (int j = 0; j < m; j++) ????????????A[i][j] -= B[i][j]; ????// Check necessary condition ????// for condition for ????// existence of full countOpsation ????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; ????// If countOpsation is possible ????// calculate total countOpsation ????int result = 0; ????for (int i = 0; i < n; i++) ????????result += abs(A[i][0]); ????for (int j = 0; j < m; j++) ????????result += abs(A[0][j] - A[0][0]); ????return (result); } // Driver code int main() { ????int A[MAX][MAX] = { {1, 1, 1}, ????????????????????????{1, 1, 1}, ????????????????????????{1, 1, 1}}; ????int B[MAX][MAX] = { {1, 2, 3}, ????????????????????????{4, 5, 6}, ????????????????????????{7, 8, 9}}; ????cout << countOps(A, B, 3, 3) ; ????return 0; } ``` ## Java ```java // Java program to find number of // countOpsation to make two matrix // equals import java.io.*; class GFG? { ????static int countOps(int A[][], int B[][], ????????????????????????int m, int n) ????{ ????????// Update matrix A[][] so that only ????????// A[][] has to be countOpsed ????????for (int i = 0; i < n; i++) ????????????for (int j = 0; j < m; j++) ????????????????A[i][j] -= B[i][j]; ????????// Check necessary condition for? ????????// condition for existence of full ????????// countOpsation ????????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; ????????// If countOpsation is possible ????????// calculate total countOpsation ????????int result = 0; ????????for (int i = 0; i < n; i++) ????????????result += Math.abs(A[i][0]); ????????for (int j = 0; j < m; j++) ????????????result += Math.abs(A[0][j] - A[0][0]); ????????return (result); ????} ????// Driver code ????public static void main (String[] args) ????{ ????????int A[][] = { {1, 1, 1}, ??????????????????????{1, 1, 1}, ??????????????????????{1, 1, 1} }; ????????int B[][] = { {1, 2, 3}, ??????????????????????{4, 5, 6}, ??????????????????????{7, 8, 9} }; ????????System.out.println(countOps(A, B, 3, 3)) ; ????} } // This code is contributed by KRV. ``` ## Python3 ```py # Python3 program to find number of # countOpsation to make two matrix # equals def countOps(A, B, m, n): ????# Update matrix A[][] so that only ????# A[][] has to be countOpsed ????for i in range(n): ????????for j in range(m): ????????????A[i][j] -= B[i][j]; ????# Check necessary condition for? ????# condition for existence of full ????# countOpsation ????for i in range(1, n): ????????for j in range(1, n): ????????????if (A[i][j] - A[i][0] - ????????????????A[0][j] + A[0][0] != 0): ????????????????return -1; ????# If countOpsation is possible ????# calculate total countOpsation ????result = 0; ????for i in range(n): ????????result += abs(A[i][0]); ????for j in range(m): ????????result += abs(A[0][j] - A[0][0]); ????return (result); # Driver code if __name__ == '__main__': ????A = [[1, 1, 1], ?????????[1, 1, 1], ?????????[1, 1, 1]]; ????B = [[1, 2, 3], ?????????[4, 5, 6], ?????????[7, 8, 9]]; ????print(countOps(A, B, 3, 3)); # This code is contributed by Rajput-Ji ``` ## C# ```cs // C# program to find number of // countOpsation to make two matrix // equals using System; class GFG? { ????static int countOps(int [,]A, int [,]B, ????????????????????????int m, int n) ????{ ????????// Update matrix A[][] so that only ????????// A[][] has to be countOpsed ????????for (int i = 0; i < n; i++) ????????????for (int j = 0; j < m; j++) ????????????????A[i, j] -= B[i, j]; ????????// Check necessary condition for? ????????// condition for existence of full ????????// countOpsation ????????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; ????????// If countOpsation is possible ????????// calculate total countOpsation ????????int result = 0; ????????for (int i = 0; i < n; i++) ????????????result += Math.Abs(A[i, 0]); ????????for (int j = 0; j < m; j++) ????????????result += Math.Abs(A[0, j] - A[0, 0]); ????????return (result); ????} ????// Driver code ????public static void Main () ????{ ????????int [,]A = { {1, 1, 1}, ?????????????????????{1, 1, 1}, ?????????????????????{1, 1, 1} }; ????????int [,]B = { {1, 2, 3}, ?????????????????????{4, 5, 6}, ?????????????????????{7, 8, 9} }; ????Console.Write(countOps(A, B, 3, 3)) ; ????} } // This code is contributed by nitin mittal. ``` ## PHP ```php <?php // PHP program to find // number of countOpsation // to make two matrix equals function countOps($A, $B,? ??????????????????$m, $n) { ????$MAX = 1000; ????// Update matrix A[][] ????// so that only A[][] ????// has to be countOpsed ????for ($i = 0; $i < $n; $i++) ????????for ($j = 0; $j < $m; $j++) ????????????$A[$i][$j] -= $B[$i][$j]; ????// Check necessary condition ????// for condition for ????// existence of full countOpsation ????for ($i = 1; $i < $n; $i++) ????for ($j = 1; $j < $m; $j++) ????????if ($A[$i][$j] - $A[$i][0] -? ????????????$A[0][$j] + $A[0][0] != 0) ????????return -1; ????// If countOpsation is possible ????// calculate total countOpsation ????$result = 0; ????for ($i = 0; $i < $n; $i++) ????????$result += abs($A[$i][0]); ????for ($j = 0; $j < $m; $j++) ????????$result += abs($A[0][$j] - $A[0][0]); ????return ($result); } ????// Driver code ????$A = array(array(1, 1, 1), ???????????????array(1, 1, 1), ???????????????array(1, 1, 1)); ????$B = array(array(1, 2, 3), ???????????????array(4, 5, 6), ???????????????array(7, 8, 9)); ????echo countOps($A, $B, 3, 3) ; // This code is contributed by nitin mittal. ?> ``` **輸出**： ``` 12 ``` 時間復雜度：O（n * m）本文由 [**Shivam Pradhan（anuj_charm）**](https://www.facebook.com/anuj.charm) 提供。如果您喜歡 GeeksforGeeks 并希望做出貢獻，則還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。