C++ですべての等しい要素を持つ最大の正方形の部分行列を見つける

この問題では、N*N行列mat[]が与えられます。私たちのタスクは、すべて等しい要素を持つ最大の正方形の部分行列を見つけることです。 。

この問題では、すべての要素が同じである特定の行列から部分行列の最大サイズを見つける必要があります。

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

Input: mat[][] = {{1, 2, 1}, {1, 2, 2}, {2, 2, 2}}
Output: 2

説明 −

matrix a11, a12, a21, a22 is of size 2X2 and forms a sub-matrix with all equal elements.

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

この問題の簡単な解決策は、行列のすべての要素をトラバースしてから、同じ要素を持つすべての部分行列をチェックすることです。アルゴリズムの時間計算量はO（n ³ ）および各サブマトリックスは、O（n ² の時間計算量で作成されます。 。

別の方法 問題を解決するには、動的計画法を使用します。 ここで、サブマトリックスの最大サイズを、その位置までのすべての要素とともに格納します。このために、隣接する要素を検討し、次に、指定された条件を満たす最長の行列を検討します。 DPマトリックスの任意のセルの幅を定式化しましょう。

要素のすべての隣接が同じである場合、最も長い部分行列の値を増やします。この場合、

$ DP [i] [j] \：=\：min（DP [i-1] [j]、DP [i] [j-1]、DP [i-1] [j-1]）+ 1 $

そうでない場合は、

DP [i] [j] =1

例

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

#include<bits/stdc++.h>
#define n 4
#define m 4
using namespace std;
int findmaxSqMatSize(int mat[][m]){
   int DP[n][m];
   memset(DP, sizeof(DP), 0);
   int maxSqMatSize = 0;
   for (int i = 0 ; i < n ; i++){
      for (int j = 0 ; j < m ; j++){
         if (i == 0 || j == 0)
            DP[i][j] = 1;
         else{
            if (mat[i][j] == mat[i-1][j] && mat[i][j] == mat[i][j-1] && mat[i][j] == mat[i-1][j-1] )
               DP[i][j] = min(min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1] ) + 1;
            else DP[i][j] = 1;
         }
         maxSqMatSize = max(maxSqMatSize, DP[i][j]);
      }
   }
   return maxSqMatSize;
}
int main(){
   int mat[n][m] = { {2, 1, 4, 3},
   {5, 1, 1, 7},
   {1, 1, 1, 4},
   {9, 4, 6, 0}};
   cout<<"The maximum square sub-matrix with all equal elements is "<<findmaxSqMatSize(mat);
   return 0;
}

出力

The maximum square sub-matrix with all equal elements is 2