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

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

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

题目要求

题目描述

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

输入格式

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

接下来 $n$ 行，每行 $m$ 个整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,m}$，表示各行中的网格是否适合排兵。

输出格式

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

输入输出样例 #1

输入 #1

4 3
0 1 1
1 0 1
0 1 1
1 1 1

输出 #1

4

输入输出样例 #2

输入 #2

3 5
1 0 1 0 1
0 1 0 1 0
0 1 1 1 0

输出 #2

3

说明/提示

对于所有测试点，保证 $1 \leq n, m \leq 12$，$0 \leq a_{i,j} \leq 1$。

---

题目分析

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

思路 1：六重循环纯暴力

1. 用四重循环枚举矩形的左上角 $(i,j)$ 与右下角 $(k,l)$，其中
   $1 \le i \le k \le n,\; 1 \le j \le l \le m$。
2. 对每一个矩形，再用两重循环扫描其内部：
   • 若发现任意 $a_{x,y}=0$，立即剪枝，放弃该矩形；
   • 若全为 1，则面积 $S=(k-i+1)(l-j+1)$，更新答案。
3. 时间复杂度
   \(T_1(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k=i}^{n}\sum_{l=j}^{m}O\!\bigl((k-i+1)(l-j+1)\bigr)=O(n^3m^3).\)
   当 $n=m=12$ 时，$12^6 \approx 3 \times 10^6$，可接受。

---

思路 2：二维前缀和优化

1. 预处理二维前缀和数组
   \(\text{sum}[i][j]=\sum_{x=1}^{i}\sum_{y=1}^{j}a_{x,y},\)
   可在 $O(nm)$ 内完成。
2. 仍用四重循环枚举矩形，但借助前缀和公式 $O(1)$ 计算区域和：
   \(S(i,j,k,l)=\text{sum}[k][l]-\text{sum}[i-1][l]-\text{sum}[k][j-1]+\text{sum}[i-1][j-1].\)
3. 若 $S(i,j,k,l)=(k-i+1)(l-j+1)$，说明该矩形全为 1，更新答案。
4. 时间复杂度
   \(T_2(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k=i}^{n}\sum_{l=j}^{m}O(1)=O(n^2m^2).\)
   当 $n=m=12$ 时，$12^4 = 20\,736$，更稳。

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

---

示例代码

方法一 暴力模拟 6层循环

#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层循环

#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;
}

---

所有代码已上传至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 认证学习微信公众号