P1387可怜的20分代码求调

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