rt

最大正方形

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

    2

    #include<bits/stdc++.h>
    using namespace std;
    bool z[105][105];
    int s[105][105];
    int main()
    {
    	int n,m;
    	scanf("%d %d",&n,&m);
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=m;j++)
    		{
    			scanf("%d",&z[i][j]);
    			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+z[i][j];
    		}
    	int ans=INT_MIN;
    	for(int x=1;x<=n;x++)
    		for(int y=1;y<=m;y++)
    		{
    			for(int k=1;k<=min(n,m);k++)
    			{
    				int x1=x+k-1;
    				int y1=y+k-1;
    				int ss=s[x1][y1]-s[x1][y-1]-s[x-1][y1]+s[x-1][y-1];
    				if(ss==k*k)
    					ans=max(ans,k);
    			}
    		}
    	printf("%d",ans);
    	
    	return 0;
    }