【GESP】C++五级练习（前缀和练习） luogu-P1387 最大正方形

GESP C++ 五级练习题，经典前缀和考点。题目难度⭐⭐★☆☆，适合做前缀和基本练习，洛谷难度等级普及-。

luogu-P1387 最大正方形

题目要求

题目描述

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

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

2

---

题目分析

本题要求在一个只包含 $0$ 和 $1$ 的矩阵中找出边长最大的全 $1$ 正方形。由于矩阵规模 $N, M \le 100$，我们可以采用以下思路：

1. 二维前缀和预处理：

• 创建一个 pre_ary 数组，其中 pre_ary[i][j] 存储以 $(1, 1)$ 为左上角、$(i, j)$ 为右下角的矩形区域内所有元素的和。
• 前缀和的计算公式为：pre_ary[i][j] = pre_ary[i-1][j] + pre_ary[i][j-1] - pre_ary[i-1][j-1] + ary[i][j]。这个预处理步骤可以将任意子矩形区域的和的计算从 $O(边长^2)$ 优化到 $O(1)$。

1. 暴力枚举所有可能的正方形：

• 确定左上角：遍历矩阵的所有点 $(i, j)$ 作为潜在正方形的左上角。
• 确定右下角 (同时确定边长)：对于每个左上角 $(i, j)$，再遍历所有可能的右下角 $(k, l)$。为了确保是正方形，必须满足 (k - i + 1) == (l - j + 1)，即行数等于列数。这样 k - i + 1 就是当前正方形的边长。
• 计算区域和：利用二维前缀和，可以在 $O(1)$ 时间内计算出当前以 $(i, j)$ 为左上角、$(k, l)$ 为右下角的正方形区域内所有元素的和 sum。公式为：sum = pre_ary[k][l] - pre_ary[i-1][l] - pre_ary[k][j-1] + pre_ary[i-1][j-1]。
• 判断与更新：如果 sum 等于当前正方形的面积（即 (边长) * (边长)），则说明该正方形区域内所有元素都是 $1$。此时，更新记录最大边长的变量。

1. 最终结果：

• 在所有满足条件的全 $1$ 正方形中，找到最大边长并输出。

这种方法的优点是思路直接，通过二维前缀和优化了子矩阵求和，避免了区域求和的耗时。

复杂度分析：

• 当前代码：枚举了所有可能的矩形（左上角和右下角），再判断是否为正方形。时间复杂度为 $O(N^2 M^2)$。对于 $N,M=100$ 的数据规模，运算量约为 $10^8$，属于卡时限的边缘，可能会超时。
• 优化暴力：如果改为枚举左上角 $(i, j)$ 和边长 $len$，复杂度可降为 $O(N \cdot M \cdot \min(N, M))$，约 $10^6$ 级别，可以通过。
• 最优解：本题的最佳解法是动态规划（DP），时间复杂度仅为 $O(N \cdot M)$，不过属于六级内容了。

---

示例代码

#include <iostream>

// ary 数组用于存储输入的 01 矩阵
int ary[105][105];
// pre_ary 数组用于存储二维前缀和
// pre_ary[i][j] 表示以 (1, 1) 为左上角，(i, j) 为右下角的矩形区域内所有元素的和
int pre_ary[105][105];

int main() {
    int n, m;
    // 输入矩阵的行数 n 和列数 m
    std::cin >> n >> m;

    // 循环输入矩阵的每个元素
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            std::cin >> ary[i][j];
        }
    }

    // 计算二维前缀和
    // 递推公式：当前位置前缀和 = 上方前缀和 + 左方前缀和 - 左上方前缀和 +
    // 当前元素值
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            pre_ary[i][j] = pre_ary[i - 1][j] + pre_ary[i][j - 1] -
                            pre_ary[i - 1][j - 1] + ary[i][j];
        }
    }

    // max_sum 用于记录找到的最大正方形的边长
    // 注意：虽然变量名叫 max_sum，但在本题逻辑中它被用来存储边长
    int max_sum = 0;

    // 枚举所有可能的子矩形
    // (i, j) 表示子矩形的左上角坐标
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // (k, l) 表示子矩形的右下角坐标
            for (int k = i; k <= n; k++) {
                for (int l = j; l <= m; l++) {
                    // 判断当前子矩形是否为正方形（行数等于列数）
                    if ((k - i + 1) == (l - j + 1)) {
                        // 利用前缀和计算该子矩形内所有元素的和
                        // 公式：右下角前缀和 - 上方区域前缀和 - 左方区域前缀和
                        // + 左上方区域前缀和
                        int sum = pre_ary[k][l] - pre_ary[i - 1][l] -
                                  pre_ary[k][j - 1] + pre_ary[i - 1][j - 1];

                        // 如果子矩形的元素和等于其面积（说明该区域内全为
                        // 1），且和大于 0 (k - i + 1) * (l - j + 1)
                        // 即为该正方形的面积
                        if (sum == (k - i + 1) * (l - j + 1) && sum > 0) {
                            // 更新最大正方形的边长
                            max_sum = std::max(max_sum, k - i + 1);
                        }
                    }
                }
            }
        }
    }

    // 输出最大正方形的边长
    std::cout << max_sum << std::endl;
    return 0;
}

---

补充：动态规划（DP）解法

虽然本题主要考察二维前缀和，但使用动态规划（DP）可以达到最优的时间复杂度 $O(N \times M)$。

状态定义：

设 dp[i][j] 表示以 (i, j) 为右下角的最大全 $1$ 正方形的边长。

状态转移方程：

• 如果 ary[i][j] == 1，则 dp[i][j] 取决于它左边、上边和左上角的 dp 值： \(dp[i][j] = \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1\)
• 如果 ary[i][j] == 0，则无法构成以该点为右下角的正方形，dp[i][j] = 0。

原理： 若要在 (i, j) 构成一个边长为 $k$ 的正方形，其左、上、左上三个方向必须都至少能构成边长为 $k-1$ 的正方形（木桶效应）。

#include <iostream>
#include <algorithm>
#include <vector>

int main() {

    int n, m;
    std::cin >> n >> m;

    // dp[i][j] 表示以 (i, j) 为右下角的最大正方形边长
    // 使用 vector 动态申请，初始化为 0
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
    
    int max_side = 0;
    int val;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            std::cin >> val;
            if (val == 1) {
                // 状态转移方程：当前位置由左、上、左上的最小值决定
                // std::min({a, b, c}) 需要 C++11 支持
                dp[i][j] = std::min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
                // 更新全局最大值
                max_side = std::max(max_side, dp[i][j]);
            }
        }
    }

    std::cout << max_side << std::endl;

    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号