2개 주어짐 행렬 그리고 비 크기의 n*m . 임무는 필요한 것을 찾는 것입니다. 변환 단계 수 두 행렬이 동일해집니다. 인쇄 -1 이것이 불가능하다면.
그만큼 변환 단계는 다음과 같습니다.
- 두 개의 행렬 중 하나의 행렬을 선택합니다.
- 다음 중 하나를 선택하세요. 행/열 선택한 매트릭스의
- 선택 항목의 모든 요소를 증가시킵니다. 행/열 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]]문자열 형식 자바산출 : -1
설명 : 어떤 변환도 a와 b를 동일하게 만들지 않습니다.
접근하다:
아이디어는 증가 모든 행/열 행렬 a 는 다음과 같습니다 감소 같은 행/열 행렬 b .
이는 두 행렬을 모두 추적하는 대신 차이점을 가지고 작업할 수 있음을 의미합니다. (a[i][j] - b[i][j]). '에서 행을 증가시키면 에이' 해당 행의 모든 요소는 1씩 증가합니다. 이는 차이 행렬의 해당 행에 있는 모든 요소가 1씩 증가하는 것과 같습니다. 마찬가지로 ' 에이' 이는 차이 행렬의 해당 열에 있는 모든 요소를 1씩 증가시키는 것과 같습니다.
이를 통해 문제를 단 하나의 행렬로 작업하는 것으로 변환할 수 있습니다.
솔루션이 존재하는지 여부를 확인하십시오.
자바 이런 개념
생성 후 차이 행렬 각 셀마다 에[나는][제이] (첫 번째 행과 첫 번째 열 제외) 다음을 확인합니다.
a[i][j] - a[i][0] - a[0][j] + a[0][0] = 0.
이 방정식이 어떤 셀에도 적용되지 않으면 해가 존재하지 않는다는 결론을 즉시 내릴 수 있습니다.
이것이 작동하는 이유는 무엇입니까?
어떻게 생각해보세요 행과 열 작업은 각 셀에 영향을 미칩니다. 수행할 때 엑스 행의 작업 나 그리고 그리고 열에 대한 작업 j 에[나는][제이] (x + y)로 변경 에[나는][0] x에 의한 변경(행 연산에만 해당) a[0][j]는 y에 의한 변경(열 연산에만 해당) 및 a[0][0]은 다음의 영향을 받습니다. i행도 j열도 아님 운영. 그러므로 (x + y) - x - y + 0 = 0 유효한 솔루션을 유지해야 합니다. 이 방정식이 어떤 셀에도 적용되지 않으면 일련의 행 및 열 작업이 하나의 행렬을 다른 행렬로 변환할 수 없음을 의미합니다.
필요한 변환 수를 계산합니다.
C++필요한 변환 수를 계산하려면 다음 사항만 보면 됩니다. 첫 번째 행 그리고 첫 번째 열 왜냐하면:
- 먼저 요약하자면 |a[i][0]| 모든 i(각각의 첫 번째 열 요소)에 대해 이는 필요한 행 작업 수를 나타내기 때문입니다. 각 행에 대해 |a[i][0]|가 필요합니다. 해당 행 요소를 0으로 만드는 작업입니다.
- 그럼 요약해보자 |a[0][j] - a[0][0]| 모든 j(각 첫 번째 행 요소에서 첫 번째 요소를 뺀 값)에 대해 이는 필요한 추가 열 작업을 나타내기 때문입니다. 행 작업이 이미 이 요소에 영향을 미쳤으므로 두 번 계산되지 않도록 a[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
시간 복잡도: 오(n*m)
보조 공간: 오(1)
csv 자바에서 읽기퀴즈 만들기