C ++中的最大平方

假设我们有一个二维二进制矩阵，其中填充了0和1。我们必须找到仅包含1的最大正方形，并返回其面积。所以如果矩阵像-

然后输出将是4

为了解决这个问题，我们将遵循以下步骤-

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

• 如果n为0，则返回0

• 创建另一个订单矩阵(nxc)

• 对于i，范围为0至n – 1

• m [i，j]：=矩阵[i，j]

• ans：= m [i，j]和ans的最大值

• 对于j，范围从0到c – 1

• 对于j，范围从0到c – 1

• m [i，j]：= 1 + m [i +1，j]，m [i，j-1]，m [i +1，j-1]的最小值，

• 如果m [i，j]不为0，则

• 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