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] :=행렬[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

    의 최대값

• 응답을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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