이 문제에서는 행렬 mat이 주어집니다. 크기 mXn의 정수 값. 우리의 임무는 행렬에서 동일한 직사각형 합으로 셀을 인쇄하는 프로그램을 만드는 것입니다. .
문제 설명: 셀로 시작하고 끝나는 부분 행렬의 합이 나머지 모든 요소의 합과 같은 방식으로 행렬에서 셀을 찾을 것입니다.
셀의 경우 행렬 (a, b) 부분행렬 mat[0][0]에서 mat[a][b]로, mat[a][b]에서 mat[m][n]으로의 합은 다음과 같습니다. 나머지 모든 요소의 합계입니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
입력: 매트[][] ={ {5, 0, 2, 7}
{3, 0, 1, 0}
{1, 4, 1, 3}
{10, 0, 2, 1}}
출력: (2, 1)
설명:
요소(2,3)의 경우
부분행렬1은 - { {5, 0}
{3, 0}
{1, 4}}
부분행렬2는 - { {4, 1, 3}
{0, 2, 1}}
합계 =5 + 0 + 3 + 0 + 1 + 4 + 1 + 3 + 0 + 2 + 1 =20
나머지 요소의 합계 =2 + 7 + 1 + 0 + 10 =20
솔루션 접근 방식
문제를 해결하려면 aux1[m][n] 및 aux2[m][n]의 2개의 보조 부분행렬을 생성해야 합니다. aux1[i][j]는 (0,0)에서 (i, j)까지의 모든 요소의 합을 저장하고 aux2[i][j]는 (i,j)에서 ( n, m). 그런 다음 두 번 발생하므로 합계를 더하고 mat(i,j)를 뺍니다.
그런 다음 이 합을 행렬의 모든 요소의 합과 비교할 것입니다. 셀의 합이 행렬 합의 절반인 경우. 그런 다음 셀이 결과이고 인쇄합니다.
우리 솔루션의 작동을 설명하는 프로그램,
예시
#include <iostream>
using namespace std;
#define R 4
#define C 4
void findCellWithSameRectSum(int mat[R][C]) {
int m = R, n = C;
int aux1[m][n], aux2[m][n];
int matSum = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
aux2[i][j] = aux1[i][j] = mat[i][j];
matSum += mat[i][j];
}
}
for (int i = 1; i < m; i++) {
aux1[i][0] += aux1[i-1][0];
aux2[m-i-1][n-1] += aux2[m-i][n-1];
}
for (int j = 1; j < n; j++) {
aux1[0][j] += aux1[0][j-1];
aux2[m-1][n-j-1] += aux2[m-1][n-j];
}
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++) {
aux1[i][j] += aux1[i-1][j] + aux1[i][j-1] - aux1[i-1][j-1];
aux2[m-i-1][n-j-1] += aux2[m-i][n-j-1] + aux2[m-i-1][n-j] - aux2[m-i][n-j];
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (matSum == 2 * (aux1[i][j] + aux2[i][j] - mat[i][j]))
cout << "(" << i << ", " << j << ")\t";
}
int main() {
int mat[R][C] = {{5, 0, 2, 7},
{3, 0, 1, 0},
{1, 4, 1, 3},
{10, 0, 2, 1}};
cout<<"The cells with same rectangular sums in a matrix is \n";
findCellWithSameRectSum(mat);
return 0;
} 출력
The cells with same rectangular sums in a matrix is (1, 1) (2, 1)