leetcode 221. Maximal Square

男娘i 2022-08-20 14:28 40阅读 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 0 1 0 0
    1 0 1 1 1
    1 1 1 1 1
    1 0 0 1 0

Return 4.

、

class Solution {
    	bool checkboader(vector<vector<char>>& matrix,int rightdownX,int rightdownY,int len)
    	{
    		for(int i=rightdownY-len;i<=rightdownY;i++)
    			if(matrix[i][rightdownX]=='0')
    				return false;
    		for(int i=rightdownX-len;i<=rightdownX;i++)
    			if(matrix[rightdownY][i]=='0')
    				return false;
    		return true;
    	}
    	void get_bigger(vector<vector<char>>& matrix,int leftupX,int leftupY,int&maxsquare)
    	{
    		int kk=1;
    		while(leftupX+kk<matrix[0].size()&&leftupY+kk<matrix.size()&&
    			checkboader(matrix,leftupX+kk,leftupY+kk,kk))
    			kk++;
    		//if(leftupX+kk>=matrix[0].size()||leftupY+kk>=matrix.size())
    
    		if(kk>maxsquare)
    			maxsquare=kk;
    	}
    public:
    	int maximalSquare(vector<vector<char>>& matrix) {
    		if(matrix.empty())
    			return 0;
    		if(matrix[0].empty())
    			return 0;
    		int maxsquare=0;
    		for(int i=0;i<matrix.size()-maxsquare;i++)
    			for(int j=0;j<matrix[0].size()-maxsquare;j++)
    			{
    				if(matrix[i][j]=='1')
    				{
    					get_bigger(matrix,j,i,maxsquare);
    				}
    				//cout<<i<<"  "<<j<<endl;
    			}
    			return maxsquare*maxsquare;
    	}
    };

accepted

发表评论取消回复

表情：

评论列表（有 0 条评论，40人围观）

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

相关阅读

相关 221. Maximal Square（最大的面积）

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing onl

我会带着你远行/ 2023年07月25日 09:06/ 0 赞/ 14 阅读

相关 leetcode 221. Maximal Square | 221. 最大正方形（优化的暴力解法+动态规划解法）

题目 [https://leetcode.com/problems/maximal-square/][https_leetcode.com_problems_maxima

蔚落/ 2022年10月07日 12:57/ 0 赞/ 188 阅读

相关 Maximal Square（C++最大正方形）

（1）动态规划 class Solution { public: int maximalSquare(vector<vector<cha

不念不忘少年蓝@/ 2022年09月04日 00:49/ 0 赞/ 196 阅读

相关 leetcode 221. Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all

男娘i/ 2022年08月20日 14:28/ 0 赞/ 41 阅读

相关 leetcode Maximal Square

题目 Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containi

系统管理员/ 2022年08月01日 06:12/ 0 赞/ 152 阅读

相关 leetcode 221. Maximal Square 最大正方形面积 + 动态规划DP实现

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing onl

淩亂°似流年/ 2022年06月08日 11:55/ 0 赞/ 197 阅读

相关 LeetCode:221. Maximal Square（数组中最大的正方形）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

分手后的思念是犯贱/ 2022年04月03日 09:10/ 0 赞/ 195 阅读

相关 [LeetCode] Maximal Square

[Maximal Square][Maximal Square] Given a 2D binary matrix filled with 0's and 1's, find

Love The Way You Lie/ 2021年12月03日 07:15/ 0 赞/ 151 阅读

相关 [leetcode]动态规划之Maximal Square

动态规划之Maximal Square 题目思考代码题目 [leetcode入口][leetcode] 思考之前认为dp表格的含

心已赠人/ 2021年09月29日 01:40/ 0 赞/ 366 阅读

相关 LeetCode : 221. Maximal Square 最大正方形

试题 Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containin

た入场券/ 2021年06月24日 16:11/ 0 赞/ 450 阅读