Hình vuông cực đại trong C ++

Giả sử chúng ta có một ma trận nhị phân 2D chứa các số 0 và 1. Chúng ta phải tìm hình vuông lớn nhất chỉ chứa 1 và trả về diện tích của nó. Vì vậy, nếu ma trận giống như -

Khi đó đầu ra sẽ là 4

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ans:=0, n:=số hàng, c:=số hàng

• nếu n là 0, thì trả về 0

• Tạo một ma trận thứ tự khác (n x c)

• cho tôi trong phạm vi từ 0 đến n - 1

  • cho j trong phạm vi 0 đến c - 1

    • m [i, j]:=matrix [i, j]

    • ans:=tối đa là m [i, j] và ans

• cho j trong phạm vi 0 đến c - 1

  • nếu m [i, j] không phải là 0 thì

    • m [i, j]:=1 + tối thiểu của m [i + 1, j], m [i, j-1], m [i + 1, j-1],

  • ans:=tối đa là m [i, j] và ans

• trả về ans * ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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)));
}

Đầu vào

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

Đầu ra

4