leetcode 221. Maximal Square

男娘i 2022-08-20 14:28 160阅读 0赞

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 1’s and return its area.

For example, given the following matrix:

  1. 1 0 1 0 0
  2. 1 0 1 1 1
  3. 1 1 1 1 1
  4. 1 0 0 1 0

Return 4.

  1. class Solution {
  2. bool checkboader(vector<vector<char>>& matrix,int rightdownX,int rightdownY,int len)
  3. {
  4. for(int i=rightdownY-len;i<=rightdownY;i++)
  5. if(matrix[i][rightdownX]=='0')
  6. return false;
  7. for(int i=rightdownX-len;i<=rightdownX;i++)
  8. if(matrix[rightdownY][i]=='0')
  9. return false;
  10. return true;
  11. }
  12. void get_bigger(vector<vector<char>>& matrix,int leftupX,int leftupY,int&maxsquare)
  13. {
  14. int kk=1;
  15. while(leftupX+kk<matrix[0].size()&&leftupY+kk<matrix.size()&&
  16. checkboader(matrix,leftupX+kk,leftupY+kk,kk))
  17. kk++;
  18. //if(leftupX+kk>=matrix[0].size()||leftupY+kk>=matrix.size())
  19. if(kk>maxsquare)
  20. maxsquare=kk;
  21. }
  22. public:
  23. int maximalSquare(vector<vector<char>>& matrix) {
  24. if(matrix.empty())
  25. return 0;
  26. if(matrix[0].empty())
  27. return 0;
  28. int maxsquare=0;
  29. for(int i=0;i<matrix.size()-maxsquare;i++)
  30. for(int j=0;j<matrix[0].size()-maxsquare;j++)
  31. {
  32. if(matrix[i][j]=='1')
  33. {
  34. get_bigger(matrix,j,i,maxsquare);
  35. }
  36. //cout<<i<<" "<<j<<endl;
  37. }
  38. return maxsquare*maxsquare;
  39. }
  40. };

accepted

发表评论

表情:
评论列表 (有 0 条评论,160人围观)

还没有评论,来说两句吧...

相关阅读