C++で指定された合計の部分行列を検索します

---

この問題では、サイズN * Nの2D行列と、合計とサイズの2つの変数が与えられます。私たちのタスクは、指定された合計の部分行列を見つけることです 。

要素の合計がsumに等しいsize*sizeの部分行列を見つける必要があります。

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

Input : mat[][] = {
   {1, 5, 7, 9}
   {2, 4, 6, 8}
   {1, 2, 5, 6}
   {3, 6, 9, 3}
}
sum = 22
Size = 2
Output : YES

説明 −

The submatrix of size k with sum 22 is
{5, 7}
{4, 6}

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

この問題の簡単な解決策は、可能なすべてのサイズ*サイズのサブ配列を作成し、合計を見つけて、それを指定された合計値と等しくすることです。両方が等しい場合は戻ります。

別のアプローチは、動的計画法アルゴリズムの概念を使用することです。 。このアプローチでは、現在のインデックス値までの合計を格納するDP配列を作成します。つまり、DP [i] [j]は、行インデックス0からiおよび列インデックス0からjまでの配列のすべての要素の合計を格納します。 。

このDP配列を使用して、式

を使用して任意の2つの開始インデックスと終了インデックスの合計を計算します。

$$ \ mathrm {sum（（i_s、j_s）to（i_e、j_e））\：=\：DP [i_s] [i_s] \：+ \：DP [i_e] [i_e] \：-\：DP [ i_s] [i_e] \：-\：DP [i_e] [i_s]} $$

アルゴリズム

ステップ1 −サイズ（n + 1）*（n + 1）のDP行列を作成します。

ステップ2 −行列の各要素について、現在のインデックスまでの合計を求めます。

ステップ3 − 0からnまでのすべてのインデックスについて、サイズsize*sizeの部分行列の合計を求めます。数式を使用してcurrSumに保存します。

ステップ4 − currSum ==sumの場合、trueを返します。

ステップ5 −falseを返します。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
#define N 4
bool findSubMatWithSum(int size, int sum, int mat[N][N]){
   int DP[N + 1][N + 1];
   for (int i = 0; i < N; i++)
   for (int j = 0; j < N; j++)
   DP[i + 1][j + 1] = DP[i + 1][j] + DP[i][j + 1] - DP[i][j] + mat[i][j];
   int currSum = 0;
   for (int i = 0; i < N; i++)
   for (int j = 0; j < N; j++) {
      currSum = DP[i][j] + DP[(i + size)][(j + size)] - DP[(i + size)][j] - DP[i][(j + size)];
      if (currSum == sum)
      return true;
   }
   return false;
}
int main(){
   int mat[N][N] = { { 1, 5, 7, 9 },
   { 2, 4, 6, 8 },
   { 1, 2, 5, 6 },
   { 3, 6, 9, 3 } };
   int size = 2;
   int sum = 22;
   if (findSubMatWithSum(size, sum, mat))
      cout<<"Sub-Matrix of given size having the given sum is possible!";
   else
     cout<<"Sub-Matrix of given size having the given sum is not possible!";
}

出力

Sub-Matrix of given size having the given sum is possible!