C++の行列に同じ長方形の合計を持つセルを印刷します

この問題では、行列 matが与えられます。 整数値のサイズmXnの。私たちのタスクは、行列に同じ長方形の合計を持つセルを印刷するプログラムを作成することです。 。

問題の説明： セルで開始および終了するサブマトリックスの合計が残りのすべての要素の合計と等しくなるように、マトリックス内のセルを検索します。

セルの場合、行列（a、b）サブ行列mat[0][0]からmat[a][b]およびmat[a][b]からmat[m][n]の合計は次のようになります。残りのすべての要素の合計。

問題を理解するために例を見てみましょう。

入力： mat [] [] ={{5、0、2、7}
{3、0、1、0}
{1、4、1、3}
{10、0、2、1}}

出力： （2、1）

説明：

要素（2,3）の場合

Submatrix1は-{{5、0}
{3、0}
{1、4}}

Submatrix2は-{{4、1、3}
{0、2、1}}

合計=5+ 0 + 3 + 0 + 1 + 4 + 1 + 3 + 0 + 2 + 1 =20

残りの要素の合計=2+ 7 + 1 + 0 + 10 =20

ソリューションアプローチ

この問題を解決するには、2つの補助部分行列aux1[m][n]とaux2[m][n]を作成する必要があります。 aux1 [i] [j]は（0,0）から（i、j）までのすべての要素の合計を格納し、aux2 [i] [j]は（i、j）から（ n、m）。次に、2回発生するため、合計と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)