点击查看代码
#include <iostream>
#include <algorithm> // 用于 min/max 函数（本题可省略，但建议保留以适配更多场景）
using namespace std;const int MAX_SIZE = 105; // 数组最大尺寸，适配 n/m ≤ 100 的输入
int s[MAX_SIZE][MAX_SIZE]; // 存储原始01矩阵（1-based索引，避免边界判断麻烦）
int a[MAX_SIZE][MAX_SIZE]; // 存储前缀和矩阵（同样1-based）
int n, m; // 矩阵的行数和列数
int ans = 0; // 记录最大全1正方形的边长，初始为0int main() {// 1. 输入矩阵大小和原始01矩阵cin >> n >> m;for (int i = 1; i <= n; ++i) { // 1-based索引：i从1到n，j从1到mfor (int j = 1; j <= m; ++j) {cin >> s[i][j]; // 输入0或1}}// 2. 计算前缀和矩阵for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {// 前缀和公式：当前格子值 + 左方前缀和 + 上方前缀和 - 左上重叠前缀和a[i][j] = s[i][j] + a[i][j-1] + a[i-1][j] - a[i-1][j-1];}}// 3. 枚举所有可能的正方形，用前缀和判断是否全1for (int i = 1; i <= n; ++i) { // i：正方形右下角的行坐标（1-based）for (int j = 1; j <= m; ++j) { // j：正方形右下角的列坐标（1-based）if (s[i][j] != 1) { // 若当前格子是0，不可能作为正方形的右下角，直接跳过continue;}// 枚举正方形的边长k：从当前最大ans+1开始（更小的k无需考虑），直到边界允许// 边界条件：i-k ≥ 0 且 j-k ≥ 0 → 保证正方形左上角(i-k, j-k)在矩阵内（1-based下左上角为(i-k+1, j-k+1)）for (int k = ans + 1; i - k >= 0 && j - k >= 0; ++k) {// 计算以(i,j)为右下角、边长为k的正方形内的元素和// 前缀和求子矩阵和公式：右下角和 + 左上角前一个和 - 上方和 - 左方和int sum = a[i][j] + a[i - k][j - k] - a[i - k][j] - a[i][j - k];if (sum == k * k) { // 元素和等于k² → 所有元素都是1（因为每个元素是0或1）ans = k; // 更新最大边长} else {break; // 剪枝：当前k的正方形不是全1，更大的k会包含它，也不可能是全1}}}}// 4. 输出结果cout << ans << endl;return 0;
}
用前缀和去做，对边界的讨论很精准，有利于理解边界设置和三重循环的设置和遍历方式以及去重的方式
