P1387 最大正方形 题解

· · 个人记录

P1387 最大正方形 暴力解法

题目传送门 ：P1387 最大正方形

我不知道前缀和算不算正解，但既然 AC 了就写一篇题解

正所谓暴力出奇迹. . . . . .其实我是看到 1≤n,m≤100 才想到暴力的，但 39ms 在我意料之外，开 O2 之后就 34ms。

思路

题目让我们求一个不包含 0 的最大正方形，输出边长

不包含 0 ，也就意味着这个正方形内部全是 1，那这个正方形的面积就是边长乘边长了。这个正方形内部但凡有一个 0 ，面积就会变小，那么要确定正方形内部有没有 0 ，直接在输入时求出前缀和，然后和正确的正方形面积比对一下不就好了吗？！（正确的正方形面积指在内部没有 0 的情况下正方形的面积）

到这时本题唯一的难点就解决了，接下来就只需要考虑枚举的问题，最简单的就是枚举每个点，每次以这个点为正方形的左上角，然后再设一重循环枚举正方形的边长，一旦正方形的范围超出了矩阵，就结束这层循环，否则判断正方形内部是否有 0 ，如果没有就取最大值。

Code ：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x;char ch;
    while(true){
        ch=getchar();
        if(ch>='0'&&ch<='9') break;
    }x=ch-'0';
    while(true){
        ch=getchar();
        if(ch<'0'||ch>'9') break;
        x=x*10+ch-'0';
    }return x;
}
int main()
{
    int n,m,maxn=0;n=read(),m=read();
    int sum[n+1][m+1];
    for(int i=1;i<=n;i++)
        for(int j=1,x;j<=m;j++){
            x=read();
            //sum[][]记录前缀和 
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            //k枚举正方形的边长 
            for(int k=1;k;k++){
                int x=i+k-1,y=j+k-1;
                //如果正方形的范围超出了矩阵，就结束这层循环 
                if(y<1||y>m||x<1||x>n) break;
                if(k*k==sum[x][y]-sum[i-1][y]-sum[x][j-1]+sum[i-1][j-1]) maxn=max(maxn,k);
            }
    printf("%d",maxn);
    return 0;
}

思路中关于前缀和的内容，本篇文章不做过多解释，想学习的的戳这里（此处给出的链接并不是本人的文章）