C++ 算法考级专栏
🎨 视觉封面【GESP】C++四级真题 luogu-B4415 [GESP202509 四级] 排兵布阵
GESP C++ 2025年9月四级真题,二维数组考点,难度⭐⭐★☆☆。
luogu-B4415 [GESP202509 四级] 排兵布阵
题目要求
题目描述
作为将军,你自然需要合理地排兵布阵。地图可以视为 行 列的网格,适合排兵的网格以 1 标注,不适合排兵的网格以 0 标注。现在你需要在地图上选择一个矩形区域排兵,这个矩形区域内不能包含不适合排兵的网格。请问可选择的矩形区域最多能包含多少网格?
输入格式
第一行,两个正整数 ,分别表示地图网格的行数与列数。
接下来 行,每行 个整数 ,表示各行中的网格是否适合排兵。
输出格式
一行,一个整数,表示适合排兵的矩形区域包含的最大网格数。
输入输出样例 #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说明/提示
对于所有测试点,保证 ,。
题目分析
给定一个 的 0/1 矩阵,求仅由 1 构成的最大矩形面积。
由于 ,可直接暴力枚举,也可借助前缀和优化。
思路 1:六重循环纯暴力
- 用四重循环枚举矩形的左上角 与右下角 ,其中
。 - 对每一个矩形,再用两重循环扫描其内部:
- 若发现任意 ,立即剪枝,放弃该矩形;
- 若全为 1,则面积 ,更新答案。
- 时间复杂度 当 时,,可接受。
思路 2:二维前缀和优化
- 预处理二维前缀和数组 可在 内完成。
- 仍用四重循环枚举矩形,但借助前缀和公式 计算区域和:
- 若 ,说明该矩形全为 1,更新答案。
- 时间复杂度 当 时,,更稳。
两种实现均能通过 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:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【GESP】C++四级真题 luogu-B4005 [GESP202406 四级] 黑白方块
GESP C++四级2024年6月真题。本题主要考察二维数组,多重循环操作甚至前缀和思想。暴力难度不大,前缀和优化需要点思想,整体难度⭐⭐★☆☆。本题在洛谷评定为普及-。
【GESP】C++四级练习 luogu-P5729 【深基5.例7】工艺品制作
GESP C++四级练习,二维/多维数组练习,难度★★☆☆☆。 luogu-P5729 【深基5.例7】工艺品制作 题目要求 题目描述 现有一个长宽高分别为 w,x,h 组成的实心玻璃立方体,可以认为是由 111 的数个小方块组成的,每个小方块都有一个坐标 ( i,j,...
【GESP】C++四级练习 luogu-P2550 [AHOI2001] 彩票摇奖
GESP C++四级练习,二维/多维数组练习,难度★★☆☆☆。 luogu-P2550 [AHOI2001] 彩票摇奖 题目要求 题目描述 为了丰富人民群众的生活、支持某些社会公益事业,北塔市设置了一项彩票。该彩票的规则是: 1. 每张彩票上印有 7 个各不相同的号码,...
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

