C++ 프로그램에서 모두 1인 최대 크기의 직사각형 이진 부분행렬

이 문제에서는 0/1과 같은 온라인 이진수를 포함하는 크기 n*m의 2차원 행렬 bin[][]이 제공됩니다. 우리의 임무는 모두 1이고 최대 면적을 반환하는 최대 크기의 직사각형 이진 부분행렬을 찾는 프로그램을 만드는 것입니다.

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

입력

bin[][] = {
   {1, 0, 1, 1, 1}
   {0, 1, 1, 1, 1}
   {0, 0, 1, 1, 1}
   {1, 1, 1, 1, 1}
}

출력

12

설명

이 직사각형의 경우 최대 면적입니다.

1, 1, 1
1, 1, 1
1, 1, 1
1, 1, 1

솔루션 접근 방식

문제를 해결하려면 1로만 구성된 가능한 가장 큰 직사각형 부분행렬을 찾아야 합니다. 그리고 이를 위해서는 현재 행이 직사각형으로 만들어질 때까지의 최대 면적을 찾아야 합니다.

현재 행까지의 영역은 열의 현재 요소까지 연속된 수를 먼저 구하여 계산됩니다. 그리고 우리는 한 번 같거나 더 큰 수를 가진 요소를 고려할 것입니다. 즉, 모든 숫자가 다른 경우 가장 작은 것으로 간주합니다. 지금까지 가장 큰 영역을 가진 행이 결과가 됩니다.

예시

우리 솔루션의 작동을 설명하는 프로그램

#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 5
int calcAreaTillRow(int row[]){
   stack<int> area1s;
   int tos;
   int maxArea = 0;
   int curArea = 0;
   int i = 0;
   while (i < C) {
      if (area1s.empty() || row[area1s.top()] <= row[i])
         area1s.push(i++);
      else {
         tos = row[area1s.top()];
         area1s.pop();
         curArea = tos * i;
         if (!area1s.empty())
            curArea = tos * (i − area1s.top() − 1);
         maxArea = max(curArea, maxArea);
      }
   }
   while (!area1s.empty()) {
      tos = row[area1s.top()];
      area1s.pop();
      curArea = tos * i;
      if (!area1s.empty())
         curArea = tos * (i − area1s.top() − 1);
      maxArea = max(curArea, maxArea);
   }
   return maxArea;
}
int calcmaxRecSubMat1(int bin[][C]){
   int result = calcAreaTillRow(bin[0]);
   for (int i = 1; i < R; i++) {
      for (int j = 0; j < C; j++)
      if (bin[i][j])
         bin[i][j] += bin[i − 1][j];
      result = max(result, calcAreaTillRow(bin[i]));
   }
   return result;
}
int main(){
   int bin[][C] = {
      {1, 0, 1, 1, 1},
      {0, 1, 1, 1, 1},
      {0, 0, 1, 1, 1},
      {1, 1, 1, 1, 1}
   };
   cout<<"The area of maximum size rectangle binary sub−matrix with all 1s is "<<calcmaxRecSubMat1(bin);
   return 0;
}

출력

The area of maximum size rectangle binary sub-matrix with all 1s is 12