最大正方形_输入说明 : 首先输入矩阵的行数m、列数n 然后输入m行,每行n个字符0或1,中间无空格-程序员宅基地

问题描述 :
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4

输入说明 :
首先输入矩阵的行数m、列数n
然后输入m行，每行n个字符0或1，中间无空格分隔。

输出说明 :
输出一个整数

输入范例 :
4 5
10100
10111
11111
10010

输出范例 :
4

//dp没用到  遇到一个1  就往前找  遇到0就停止
#include<iostream>
#include<vector>

using namespace std;
int maxSquare(vector<vector<int>> matrix){
    
	if(matrix.size()==0){
    
		return 0;
	}
	int res=0;
	vector<vector<int>> dp(matrix.size(),vector<int>(matrix[0].size()));
	for(int i=0;i<matrix.size();i++){
    
		if(matrix[i][0]==1){
    
			res=1;
			dp[i][0]=1;
		}else{
    
			dp[i][0]=0;
		}
	}
	for(int i=0;i<matrix[0].size();i++){
    
		if(matrix[0][i]==1){
    
			res=1;
			dp[0][i]=1;
		}else{
    
			dp[0][i]=0;
		}
	}
	
	for(int i=1;i<matrix.size();i++){
    
		for(int j=1;j<matrix[0].size();j++){
    
			if(matrix[i][j]==0){
    
				dp[i][j]=0;
			}else{
    
				int bian=min(j,i);
				int m=i-1;
				int n=j-1;
				while(bian--){
    
					int flag=0;
					int tag=0;
					for(int k=m;k<=i;k++){
    
						if(matrix[k][n]==0){
    
							flag=1;
							break;
						}
					}
					for(int l=n;l<=j;l++){
    
						if(matrix[m][l]==0){
    
							tag=1;
							break;
						}
					}
					m--;
					n--;
					if(tag||flag){
    
						break;
					}
				}
				if((min(i,j)-bian)*(min(i,j)-bian)>res){
    
					res=(min(i,j)-bian)*(min(i,j)-bian);
				}
			}
		}
	}
	return res;
}
int main(){
    
	int m,n;
	cin>>m;
	cin>>n;
	vector<int> tmp;
	char temp;
	vector<vector<int>> matrix;
	for(int i=0;i<m;i++){
    
		for(int j=0;j<n;j++){
    
			cin>>temp;
			tmp.push_back(temp-'0');
		}
		matrix.push_back(tmp);
		tmp.clear();
	}
	int res=maxSquare(matrix);
	cout<<res;
}

本文链接：https://blog.csdn.net/ZhEnG_jIe_YuAn/article/details/108203417

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

AndroidStudio无代码高亮解决办法_android studio 高亮-程序员宅基地

文章浏览阅读2.8k次。AndroidStudio 升级到 4.2.2 版本后，没有代码高亮了，很蛋疼。解决办法是：点开上方的 File，先勾选 Power Save Mode 再取消就可以了。_android studio 高亮

swift4.0 valueForUndefinedKey:]: this class is not key value coding-compliant for the key unity.'_forundefinedkey swift4-程序员宅基地

文章浏览阅读1k次。使用swift4.0整合Unity出现[ valueForUndefinedKey:]: this class is not key value coding-compliant for the key unity.'在对应属性前加@objc 即可。或者调回swift3.2版本_forundefinedkey swift4

Spring Security2的COOKIE的保存时间设置_springsecurity 设置cookie失效时间-程序员宅基地

文章浏览阅读1.3k次。http auto-config="true" access-denied-page="/common/403.htm"> intercept-url pattern="/login.**" access="IS_AUTHENTICATED_ANONYMOUSLY"/> form-login login-page="/login.jsp" defau_springsecurity 设置cookie失效时间

view滑动冲突解决实战篇2（外部拦截法）_viewpage2外部拦截事件-程序员宅基地

文章浏览阅读1.1k次。继上篇内部拦截法需求还是跟上篇一样。只不过这次用外部拦截法来解决；只要在父容器添加如下代码就可以解决了滑动冲突，很简单，套模板就行 // 分别记录上次滑动的坐标(onInterceptTouchEvent) private int mLastXIntercept = 0; private int mLastYIntercept = 0; @Override public bo_viewpage2外部拦截事件

汇编堆栈变量存储指针_汇编语言栈指针-程序员宅基地

文章浏览阅读2.5k次，点赞7次，收藏9次。本文章系作者原创，未经许可，不得转载。汇编堆栈变量存储指针先说栈的概念，栈其实也是一种。。。。。先说内存的概念吧。。。。。额先说计算机吧，简单来说的话，可以把计算机理解成由CPU，内存，硬盘组成，而CPU内部又包括一种叫做内部寄存器的东西，包括数据寄存器： AX,BX,CX,DX；段寄存器： CS,DS,ES,SS；指针与变址寄存器SP,BP,SI,DI； ..._汇编语言栈指针

架构师之路：从码农到架构师你差了哪些_web架构师-程序员宅基地

文章浏览阅读1w次，点赞14次，收藏56次。转载自架构师之路：从码农到架构师你差了哪些 Web应用，最常见的研发语言是Java和PHP。后端服务，最常见的研发语言是Java和C/C++。大数据，最常见的研发语言是Java和Python。可以说，Java是现阶段中国互联网公司中，覆盖度最广的研发语言，掌握了Java技术体系，不管在成熟的大公司，快速发展的公司，还是创业阶段的公司，都能有立足之地。有..._web架构师