OneCoder Avatar
OneCodercoderli.com · 1024 篇博文
四级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++四级真题 luogu-B4415 [GESP202509 四级] 排兵布阵

📅 2025-10-05·✍️ OneCoder·计算中...·⏱️ 11 分钟

GESP C++ 2025年9月四级真题,二维数组考点,难度⭐⭐★☆☆。

luogu-B4415 [GESP202509 四级] 排兵布阵

题目要求

题目描述

作为将军,你自然需要合理地排兵布阵。地图可以视为 行 列的网格,适合排兵的网格以 1 标注,不适合排兵的网格以 0 标注。现在你需要在地图上选择一个矩形区域排兵,这个矩形区域内不能包含不适合排兵的网格。请问可选择的矩形区域最多能包含多少网格?

输入格式

第一行,两个正整数 ,分别表示地图网格的行数与列数。

接下来 行,每行 个整数 ,表示各行中的网格是否适合排兵。

输出格式

一行,一个整数,表示适合排兵的矩形区域包含的最大网格数。

输入输出样例 #1

输入 #1
PLAINTEXT5 行
4 3
0 1 1
1 0 1
0 1 1
1 1 1
输出 #1
PLAINTEXT1 行
4

输入输出样例 #2

输入 #2
PLAINTEXT4 行
3 5
1 0 1 0 1
0 1 0 1 0
0 1 1 1 0
输出 #2
PLAINTEXT1 行
3

说明/提示

对于所有测试点,保证 ,。


题目分析

给定一个 的 0/1 矩阵,求仅由 1 构成的最大矩形面积。
由于 ,可直接暴力枚举,也可借助前缀和优化。

思路 1:六重循环纯暴力

  1. 用四重循环枚举矩形的左上角 与右下角 ,其中
    。
  2. 对每一个矩形,再用两重循环扫描其内部:
    • 若发现任意 ,立即剪枝,放弃该矩形;
    • 若全为 1,则面积 ,更新答案。
  3. 时间复杂度 当 时,,可接受。

思路 2:二维前缀和优化

  1. 预处理二维前缀和数组 可在 内完成。
  2. 仍用四重循环枚举矩形,但借助前缀和公式 计算区域和:
  3. 若 ,说明该矩形全为 1,更新答案。
  4. 时间复杂度 当 时,,更稳。

两种实现均能通过 GESP 四级数据范围。


示例代码

方法一 暴力模拟 6层循环

C++52 行
#include <iostream>

int num_ary[15][15]; // 存储地图:1 表示可排兵,0 表示不可排兵
int main() {
    int n, m;
    std::cin >> n >> m; // 读入行数 n 和列数 m
    // 读入地图数据
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cin >> num_ary[i][j];
        }
    }

    int max_count = 0; // 记录最大合法矩形中的网格数

    // 枚举矩形左上角 (i,j)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 枚举矩形右下角 (k,l),要求 k≥i,l≥j
            for (int k = i; k < n; k++) {
                for (int l = j; l < m; l++) {
                    int count = 0;    // 当前矩形内 1 的个数
                    bool allOne = true; // 假设当前矩形全为 1

                    // 检查矩形内部是否全为 1
                    for (int x = i; x <= k; x++) {
                        for (int y = j; y <= l; y++) {
                            if (num_ary[x][y] == 1) {
                                count++; // 统计 1 的个数
                            } else {
                                allOne = false; // 出现 0,标记不合法
                                count = 0;        // 面积归零
                                break;            // 提前退出内层循环
                            }
                        }
                        if (!allOne) {
                            break; // 提前退出外层循环
                        }
                    }

                    // 若矩形合法,则尝试更新答案
                    if (allOne) {
                        max_count = std::max(max_count, count);
                    }
                }
            }
        }
    }

    std::cout << max_count << std::endl; // 输出最大网格数
    return 0;
}

方法二 前缀和 4层循环

C++46 行
#include <iostream>

// 存储地图:1 表示可排兵,0 表示不可排兵
int num_ary[15][15];
// 存储二维前缀和,sum_ary[i][j] 表示从 (1,1) 到 (i,j) 矩形区域内所有元素的和
int sum_ary[15][15];
int main() {
    int n, m;
    std::cin >> n >> m; // 读入行数 n 和列数 m

    // 读入地图数据并同时计算二维前缀和
    // 注意:这里下标从 1 开始,便于前缀和计算
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            std::cin >> num_ary[i][j];
            // 二维前缀和计算公式:当前格 = 上方格 + 左方格 - 左上方格(避免重复) + 当前值
            sum_ary[i][j] = sum_ary[i - 1][j] + sum_ary[i][j - 1] - sum_ary[i - 1][j - 1] + num_ary[i][j];
        }
    }

    int max_count = 0; // 记录最大合法矩形中的网格数

    // 枚举矩形左上角 (i,j)
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 枚举矩形右下角 (k,l),要求 k≥i,l≥j
            for (int k = i; k <= n; k++) {
                for (int l = j; l <= m; l++) {
                    // 利用二维前缀和公式计算子矩阵 (i,j) 到 (k,l) 的元素和
                    // 公式:sum(i,j,k,l) = sum[k][l] - sum[k][j-1] - sum[i-1][l] + sum[i-1][j-1]
                    int temp_sum = sum_ary[k][l] - sum_ary[k][j - 1] - sum_ary[i - 1][l] + sum_ary[i - 1][j - 1];

                    // 矩形面积 = 行数 * 列数 = (k-i+1) * (l-j+1)
                    // 如果元素和等于矩形面积,说明矩形内全为 1(每个格子都是 1)
                    if (temp_sum == (k - i + 1) * (l - j + 1)) {
                        // 更新最大合法矩形的面积
                        max_count = std::max(max_count, temp_sum);
                    }
                }
            }
        }
    }

    std::cout << max_count << std::endl; // 输出最大网格数
    return 0;
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!