C++の特定の2D配列の最小合計部分行列

行列を形成する整数要素の2次元配列が与えられます。タスクは、そのように形成された行列から部分行列を引き出すことによって、最小合計のカウントを計算することです。

このためのさまざまな入出力シナリオを見てみましょう-

で- int matrix [size] [size] ={{2、3、-1、5}、{-2、9、-1、6}、{5、6、9、-9}、{-6、1 1、1}}

アウト- 特定の2D配列の最小和部分行列は次のとおりです。-9

説明- サイズ4x4、つまり4行4列の2次元配列が与えられます。ここで、最小の部分行列が-9になるように、与えられた行列から部分行列を見つけます。

In − int matrix [row] [column] ={{4、1、3}、{-1、-1、-1}、{6、2、3}}

アウト- 特定の2D配列の最小合計部分行列は次のとおりです。-3

説明- サイズ3x3、つまり3行3列の2次元配列が与えられます。ここで、与えられた行列からサブ行列を見つけます。これは、与えられた行列の2番目の行で達成される最小の部分行列が-3であり、部分行列のサイズが1x3、つまり1行3列になります。

以下のプログラムで使用されるアプローチは次のとおりです-

• 整数の2次元配列を入力し、さらに処理するためにデータを関数Minimum_Matrix（matrix）に渡します。

• 関数Minimum_Matrix（matrix）

  の内部

  • 一時変数をintresult=INT_MAX、int arr [row]、int total、int first、intendとして宣言します。

  • ループFORをintからtempまで、tempがcolumn未満になるまで開始します。ループ内で配列要素を0に設定します。別のループFORを、intからtemp_2まで、temp_2がcolumnより小さくなるまで開始します。ループ内で、iがrow未満になるまで、int iから0まで別のループを開始し、arr[i]をar[i] + matrix[i][temo_2]として設定します。

  • 関数Algo_Kad（arr、＆first、＆end、row）の呼び出しとしてtotalを設定します

  • 合計が結果よりも小さいかどうかを確認してから、結果を合計として設定します

  • 結果を最終出力として印刷します。

• 関数内intAlgo_Kad（int * arr、int * first、int * end、int max_size）

  • 一時変数を、int totalを0、int resultをINT_MAX、int tempを0、* end =-1

    として宣言します。

  • iがmax_size未満になるまで、ループFORをiから0まで開始します。ループ内で、totalをtotal +arr[i]として設定します。

  • IFの合計が0より大きいことを確認してから、合計を0に設定し、温度をi+1に設定します。

  • それ以外の場合は、結果よりも合計が少ないことを確認してから、結果を合計に設定し、*最初に一時的に、*終了してi

  • ここで、IF * endが-1に等しくないことを確認してから、結果を返します。

  • 結果をarr[0]に設定し、* firstを0に、*endを0に設定します

  • iからmax_size未満になるまでループFORを開始します。ループ内で、結果よりも小さいIF arr [i]をチェックしてから、結果をarr [i]として設定し、*最初はiとして、*endはi

    として設定します。

  • 結果を返します。

例

#include <bits/stdc++.h>
using namespace std;
#define row 4
#define column 4
int Algo_Kad(int* arr, int* first, int* end, int max_size)
{
   int total = 0;
   int result = INT_MAX;
   int temp = 0;
   *end = -1;
   for(int i = 0; i < max_size; ++i)
   {
      total = total + arr[i];
      if(total > 0)
      {
         total = 0;
         temp = i + 1;
      }
      else if(total < result)
      {
         result = total;
         *first = temp;
         *end = i;
      }
   }
   if(*end != -1)
   {
      return result;
   }
   result = arr[0];
   *first = 0;
   *end = 0;

   for(int i = 1; i < max_size; i++)
   {
      if(arr[i] < result)
      {
         result = arr[i];
         *first = i;
         *end = i;
      }
   }
   return result;
}
void Minimum_Matrix(int matrix[][column])
{
   int result = INT_MAX;
   int arr[row];
   int total;
   int first;
   int end;

   for(int temp = 0; temp < column; ++temp)
   {
      memset(arr, 0, sizeof(arr));
      for(int temp_2 = temp; temp_2 < column; ++temp_2)
      {
         for(int i = 0; i < row; ++i)
         {
            arr[i] = arr[i] + matrix[i][temp_2];
         }

         total = Algo_Kad(arr, &first, &end, row);

         if(total < result)
         {
            result = total;
         }
      }
   }
   cout<<"Minimum sum submatrix in a given 2D array is: "<<result;
}
int main()
{
   int matrix[row][column] = {{2, 3, -1, 5},
                              {-2, 9, -1, 6},
                              { 5, 6, 9, -9},
                              { -6, 1, 1, 1} };
   Minimum_Matrix(matrix);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます

Minimum sum submatrix in a given 2D array is: -9