C++の最大正方形

0と1で満たされた2Dバイナリ行列があるとします。 1だけを含む最大の正方形を見つけて、その面積を返す必要があります。したがって、行列が-

その場合、出力は4になります

これを解決するには、次の手順に従います-

• ans：=0、n：=行数、c：=行数

• nが0の場合、0を返します

• 次数（n x c）の別の行列を作成します

• 0からn–1の範囲のiの場合

  • 0からc–1の範囲のjの場合

    • m [i、j]：=matrix [i、j]

    • ans：=最大m [i、j]およびans

• 0からc–1の範囲のjの場合

  • m [i、j]が0でない場合、

    • m [i、j]：=1+最小m[i+ 1、j]、m [i、j-1]、m [i + 1、j-1]、

  • ans：=最大m [i、j]およびans

• ans*ansを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maximalSquare(vector<vector<char>>& matrix) {
      int ans = 0;
      int n = matrix.size();
      if(!n)return 0;
      int c = matrix[0].size();
      vector<vector<int>> m(n, vector <int> (c));
      for(int i =0;i<n;i++){
         for(int j = 0; j<c;j++){
            m[i][j] = matrix[i][j] - '0';
            ans = max(m[i][j],ans);
         }
      }
      for(int i =n-2;i>=0;i--){
         for(int j =1;j<c;j++){
            if(m[i][j]){
               m[i][j] = 1 + min({m[i+1][j],m[i][j-1],m[i+1][j-1]});
            }
            ans = max(ans,m[i][j]);
         }
      }
      return ans*ans;
   }
};
main(){
   vector<vector<char>> v = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},         {'1','0','0','1','0'}};
   Solution ob;
   cout << ((ob.maximalSquare(v)));
}

入力

[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

出力

4