C++에서 모든 요소가 동일한 최대 제곱 부분 행렬 찾기

<시간/>

이 문제에서는 N*N 행렬 mat[]가 주어집니다. 우리의 임무는 모든 요소가 동일한 최대 제곱 부분행렬을 찾는 것입니다. .

이 문제에서는 모든 요소가 동일한 주어진 행렬에서 부분행렬의 최대 크기를 찾아야 합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

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

설명 -

matrix a₁₁, a₁₂, a₂₁, a₂₂ 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