202509-排兵布阵(luogu-B4415)

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

输出 #1

输入输出样例 #2

输入 #2

输出 #2

说明/提示

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

题目分析

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

思路 1：六重循环纯暴力

用四重循环枚举矩形的左上角 $(i,j)$ 与右下角 $(k,l)$ ，其中
$1 \le i \le k \le n,\; 1 \le j \le l \le m$ 。
对每一个矩形，再用两重循环扫描其内部：
- 若发现任意 $a_{x,y}=0$ ，立即剪枝，放弃该矩形；
- 若全为 1，则面积 $S=(k-i+1)(l-j+1)$ ，更新答案。
时间复杂度
$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：二维前缀和优化

预处理二维前缀和数组
$\text{sum}[i][j]=\sum_{x=1}^{i}\sum_{y=1}^{j}a_{x,y},$
可在 $O(nm)$ 内完成。
仍用四重循环枚举矩形，但借助前缀和公式 $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].$
若 $S(i,j,k,l)=(k-i+1)(l-j+1)$ ，说明该矩形全为 1，更新答案。
时间复杂度
$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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

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

最后更新于 2025年10月13日

202506-排序(luogu-B4361)202509-最长连续段(luogu-B4416)