C++プログラムのすべてが1の最大サイズの長方形のバイナリサブ行列

この問題では、オンラインの2進数（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だけで構成される可能な限り最大の長方形のサブマトリックスを見つける必要があります。このためには、現在の行が長方形で構成されるまでの最大面積を見つける必要があります。

現在の行までの面積は、最初に列の現在の要素までの連続したものの数を見つけることによって計算されます。また、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