给定两个阶数为n*m的矩阵A和B。任务是找到所需的变换步骤数，使两个矩阵相等，如果不可能，请打印-1。 转换步骤如下： i） 从两个矩阵中选择任意一个矩阵。 ii）选择所选矩阵的任一行/列。 iii）将select行/列的每个元素增加1。 例如：
null
Input : A[2][2]: 1 1 1 1B[2][2]: 1 2 3 4Output : 3Explanation :1 1 -> 1 2 -> 1 2 -> 1 21 1 -> 1 2 -> 2 3 -> 3 4Input :A[2][2]: 1 1 1 0B[2][2]: 1 2 3 4Output : -1Explanation : 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 1B[2][2] : 1 2 3 4After subtraction, A[][] becomes,A[2][2] : 0 -1 -2 -3
-> 对于每一次转换，第1行/第1列中的任何一个元素都必须被更改，对于其他第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 transformedfor (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 transformationfor (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 transformationresult = 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);
C++
// 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 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
# 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#
// 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 program to find// number of countOpsation// to make two matrix equalsfunction 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.?>
Javascript
<script> // JavaScript program to find number of // countOpsation to make two matrix // equals function countOps(A, B, m, n) { // Update matrix A[][] so that only // A[][] has to be countOpsed for ( var i = 0; i < n; i++) for ( var j = 0; j < m; j++) A[i][j] -= B[i][j]; // Check necessary condition for // condition for existence of full // countOpsation for ( var i = 1; i < n; i++) for ( var 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 var result = 0; for ( var i = 0; i < n; i++) result += Math.abs(A[i][0]); for ( var j = 0; j < m; j++) result += Math.abs(A[0][j] - A[0][0]); return (result); } // Driver code var A = [ [1, 1, 1], [1, 1, 1], [1, 1, 1] ]; var B = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]; document.write(countOps(A, B, 3, 3)) ; </script> |
输出：
12
时间复杂度：O（n*m） 本文由 希瓦姆·普拉丹（anuj_charm） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
