csp信奥赛C++高频考点专项训练之前缀和差分 --【二维前缀和】：最大正方形

csp信奥赛C++高频考点专项训练之前缀和&差分 --【二维前缀和】：最大正方形

题目描述

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

保证矩阵里有至少一个1 11。

输入格式

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

输出格式

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

输入输出样例 1

输入 1

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

输出 1

2

思路分析

使用二维前缀和快速计算任意子矩阵的和。对于全1正方形，其内部所有元素和为边长的平方。
枚举所有可能的正方形左上角(i,j)和边长len，利用前缀和公式
sum = s[i+len-1][j+len-1] - s[i-1][j+len-1] - s[i+len-1][j-1] + s[i-1][j-1]
判断是否等于len*len，记录最大边长即可。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn,m,a,s[105][105],ans=0;// s为前缀和数组，ans记录最大边长intmain(){cin>>n>>m;// 读入行数列数for(inti=1;i<=n;i++)for(intj=1;j<=m;j++){cin>>a;// 读入当前值0/1s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a;// 计算二维前缀和}// 枚举左上角和边长for(inti=1;i<=n;i++)for(intj=1;j<=m;j++){for(intlen=1;i+len-1<=n&&j+len-1<=m;len++){intsum=s[i+len-1][j+len-1]-s[i-1][j+len-1]-s[i+len-1][j-1]+s[i-1][j-1];// 子矩阵和if(sum==len*len)ans=max(ans,len);// 全1则更新答案}}cout<<ans<<endl;// 输出结果return0;}

功能分析

• 输入：整数n,m和n×m的 0/1 矩阵。
• 前缀和构建：s[i][j]存储从(1,1)到(i,j)的矩形内 1 的个数。
• 枚举判断：三层循环枚举左上角(i,j)和边长len，通过前缀和O(1)求得子矩阵和，若等于len²则说明该正方形全为 1，更新最大边长。
• 输出：最大全 1 正方形的边长。
• 复杂度：O(n·m·min(n,m))，最坏100³ = 1e6，。

【完整系列请查看专栏】：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++提高组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}