P1387 最大正方形

题目描述

在一个n×m 的只包含 0 和 1 的矩阵里找出一个不包含 0 的最大正方形，输出边长。

输入格式

输入文件第一行为两个整数n,m(1≤n,m≤100)，接下来 n 行，每行 m 个数字，用空格隔开，0 或 1。

输出格式

一个整数，最大正方形的边长。

输入输出样例

输入 #1

4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1

输出 #1

2

代码

#include<iostream>
#include<algorithm>
using namespace std;
int a[102][102];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){//输入n行m列个包含0和1的数
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==1){//计算二维数组每一行的前缀和
				a[i][j]=a[i][j-1]+1;
			}else a[i][j]=a[i][j-1];
		}
	} 
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){//计算二维数组每一列的前缀和。
			 a[j][i]=a[j][i]+a[j-1][i];
		}
	} 
	int mm=1;//统计最大的正方形的边长，最小为1。
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){//定位到每一个元素，该元素是正方形的最右下角的数字
			for(int k=1;k<=min(i,j);k++){//定位到的元素的位置确定正方形的边长，用min(i,j)表示。
				int t=a[i][j]-a[i][j-k]-a[i-k][j]+a[i-k][j-k];//通过最右下角的元素，以及要求正方形的边长求得矩形的总和。
				if(t==k*k&&mm<=k){//如果求得的总和等于边长的长度，则是要求的正方形，并且寻找最大的正方形边长。
					mm=k;
				}
//				cout<<t<<"\n";
			}
		}
	} 
	cout<<mm;
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout<<a[i][j]<<" "; 
//		}cout<<"\n";
//	} 
	return 0;
}