2515 最大的以1为边界的正方形
大约 3 分钟
2515 最大的以1为边界的正方形
【算法】 二维前缀和、枚举
【C++】 二维数组、二维前缀和
【难度】 普及/提高−
一、题目简述
给定一个 的 0/1 矩阵(),求边界全为 1 的最大正方形子网格的元素个数(即面积)。如果不存在这样的正方形,返回 0。
例如下面这个 矩阵,中心为 0 但边框全为 1,答案为 :
1 1 1
1 0 1
1 1 1二、解题思路
2.1 数据规模分析
,这是关键信息。正方形边长最多为 。枚举所有可能的正方形:
- 边长 : 种
- 左上角 : 种
- 总枚举量:,完全可行
因此不需要复杂的 DP 或搜索,直接暴力枚举即可。
2.2 用二维前缀和快速判断边框
暴力枚举需要判断一个正方形的四条边是否全为 1。如果每次逐格检查,复杂度会变成 。我们用二维前缀和来 判断。
对于正方形左上角 ,边长 ,其四条边分别为:
- 上边: 到
- 下边: 到
- 左边: 到
- 右边: 到
用前缀和查询每条边的和,如果等于 ,说明该边全为 1。四条边都全为 1 时,正方形边框合法。
注意:四个角会被两条边各算一次,但不影响判断——我们只是分别检查每条边是否全 1。
2.3 枚举策略
从大到小枚举边长 (从 到 1),一旦找到合法的正方形,直接输出 并结束。这样可以保证第一个找到的就是最大的。
2.4 手动模拟
矩阵:
1 1 1
1 0 1
1 1 1前缀和:
0 0 0 0
0 1 2 3
0 2 3 5
0 3 5 8枚举边长 3(),左上角 ,右下角 :
- 上边:
query(1,1,1,3)= 3 - 下边:
query(3,1,3,3)= 3 - 左边:
query(1,1,3,1)= 3 - 右边:
query(1,3,3,3)= 3
四条边都全 1,输出 。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int pre[N][N];
// 查询子矩阵 (x1,y1) 到 (x2,y2) 的元素和
int query(int x1, int y1, int x2, int y2) {
return pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int x;
cin >> x;
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + x;
}
}
int sz = min(n, m);
// 从大到小枚举边长
for (int len = sz; len >= 1; len--) {
for (int i = 1; i + len - 1 <= n; i++) {
for (int j = 1; j + len - 1 <= m; j++) {
int x2 = i + len - 1, y2 = j + len - 1;
int top = query(i, j, i, y2); // 上边
int bottom = query(x2, j, x2, y2); // 下边
int left = query(i, j, x2, j); // 左边
int right = query(i, y2, x2, y2); // 右边
if (top == len && bottom == len && left == len && right == len) {
cout << len * len << endl;
return 0;
}
}
}
}
cout << 0 << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。枚举边长 ,枚举左上角 ,每次 前缀和查询。最坏情况 ,轻松通过。
- 空间复杂度:。存储二维前缀和数组。
五、优化方向(拓展)
- 预处理行/列连续 1:可以预先计算每个位置向右和向下连续 1 的个数,判断边是否全 1 只需 且无需前缀和。
- 更大的数据范围:如果 , 无法通过,需要用 DP 或二分答案进一步优化。但本题 的规模枚举即可。
- 边框和公式:也可以用"整个正方形和 - 内部正方形和"直接算出边框和,如果等于 (当 时)则边框全 1,只需一次前缀和查询。
