最大正方形-二维前缀和

题目:

https://www.luogu.com.cn/problem/P1387

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

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[107][107],b[107][107];
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",&a[i][j]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
             if(i==1&&j==1)
            {
                if(a[i][j])
                    b[i][j]=1;
                else
                    b[i][j]=0;
            }
            else
            {
                if(a[i][j])
                    b[i][j]=min(min(b[i-1][j],b[i][j-1]),b[i-1][j-1])+1;

            }
        }

    }
    int mm=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        { mm=max(mm,b[i][j]);
        }
    }
       printf("%d\n",mm);
}

 

上一篇:107-逻辑运算符


下一篇:(数据科学学习手札107)在Python中利用funct实现链式风格编程