[面试题] GESP C++五级前缀和算法实战：洛谷P1387最大正方形题解

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

题目要求

题目描述

在一个的只包含和的矩阵里找出一个不包含的最大正方形，输出边长。 保证矩阵里有至少一个。

输入格式

输入文件第一行为两个整数，接下来行，每行个数字，用空格隔开，或。

输出格式

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

输入输出样例 #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正方形。由于矩阵规模，我们可以采用以下思路：

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]。这个预处理步骤可以将任意子矩形区域和的计算从优化到。

2. 枚举所有可能的正方形：

   • 确定左上角：遍历矩阵的所有点 (i， j) 作为潜在正方形的左上角。
   • 确定右下角 (同时确定边长)：对于每个左上角 (i， j)，再遍历所有可能的右下角 (k, l)。为了确保是正方形，必须满足 (k - i + 1) == (l - j + 1)，即行数等于列数。这样 k - i + 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。此时，更新记录最大边长的变量。

3. 最终结果：

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

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

复杂度分析：

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

示例代码

#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[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) 构成一个边长为 L 的正方形，其左、上、左上三个方向必须都至少能构成边长为 L-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;
}

---

“luogu-”系列题目可在洛谷题库进行在线评测。 “bcqm-”系列题目可在编程启蒙题库进行在线评测。 想要系统学习更多C++编程技巧与GESP认证知识，可以访问我们的专题页面获取结构化学习资源。