In các ô có tổng hình chữ nhật giống nhau trong một ma trận trong C ++

Trong bài toán này, chúng ta được đưa ra một ma trận mat có kích thước mXn của các giá trị nguyên. Nhiệm vụ của chúng tôi là tạo một chương trình để In các ô có các tổng hình chữ nhật giống nhau trong một ma trận .

Mô tả sự cố: Chúng ta sẽ tìm một ô trong ma trận theo cách mà tổng của ma trận con bắt đầu và kết thúc bằng ô bằng tổng của tất cả các phần tử còn lại.

Đối với một ô, tổng của ma trận (a, b) mat ma trận con [0] [0] thành mat [a] [b] và mat [a] [b] mat [m] [n] bằng tổng của tất cả các phần tử còn lại.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: mat [] [] ={{5, 0, 2, 7}
{3, 0, 1, 0}
{1, 4, 1, 3}
{10, 0, 2, 1}}

Đầu ra: (2, 1)

Giải thích:

Đối với phần tử (2,3)

Submatrix1 là - {{5, 0}
{3, 0}
{1, 4}}

Submatrix2 là - {{4, 1, 3}
{0, 2, 1}}

Tính tổng =5 + 0 + 3 + 0 + 1 + 4 + 1 + 3 + 0 + 2 + 1 =20

Tổng phần còn lại của các phần tử =2 + 7 + 1 + 0 + 10 =20

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề, chúng ta cần tạo 2 ma trận con bổ trợ là aux1 [m] [n] và aux2 [m] [n]. Aux1 [i] [j] sẽ lưu trữ tổng của tất cả các phần tử từ (0,0) đến (i, j) và aux2 [i] [j] sẽ lưu trữ tổng của tất cả các phần tử từ (i, j) đến ( n, m). Sau đó, chúng tôi sẽ cộng cả tổng và trừ mat (i, j) vì nó sẽ xảy ra hai lần.

Sau đó ta sẽ so sánh tổng này với tổng tất cả các phần tử của ma trận. Nếu tổng tại ô bằng một nửa tổng của ma trận. Sau đó, ô là kết quả và chúng tôi sẽ in nó.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

The cells with same rectangular sums in a matrix is
(1, 1)           (2, 1)