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;
}