GESP 题解库 / 5 级题解 / [GESP202406 五级] 黑白格 · 第 12 / 23 题
GESP202406 五级 · P10719 · 中等

黑白格

求至少包含 k 个黑格的最小子矩形面积,无解输出 0。

📊
n, m ≤ 100
网格规模
🔢
int
数值类型
⚡
O(n²m²)
时间复杂度
🎯
二维前缀和 + 枚举
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定 n 行 m 列的 01 网格(0 白、1 黑)。求至少包含 k 个黑色格子的子矩形中,包含格子总数的最小值;若不存在则输出 0。

例:4 × 5 网格、k = 5 时,最小子矩形是第 2~4 行、第 4~5 列,共 6 个格子(其中 6 个黑格)。

💡
人话翻译:枚举所有子矩形,挑出"黑格数 ≥ k"的那些,取其中面积最小的。关键工具是二维前缀和——它能让"某个子矩形里有几个黑格"这个查询变成 O(1)。

🔍 关键词提取

二维前缀和枚举矩形边界最小面积可行性

已知条件

项目说明
输入第一行 n、m、k;随后 n 行 01 串
输出最小子矩形的格子数,无解输出 0
数据范围1 ≤ n, m ≤ 100
k 的范围1 ≤ k ≤ n × m
目标黑格数 ≥ k 且面积最小

需要解决的问题

02
思维导图
整理解题思路的全貌
⬛ 枚举边界 + 前缀和
📊 预处理
把 01 网格转成数值
建二维前缀和 pre[][]
矩形黑格数 O(1)
下标从 1 开始省特判
🔍 枚举矩形
上边界 r1、下边界 r2
左边界 c1、右边界 c2
面积 = 行数 × 列数
共约 2500 万个候选
✅ 判定与更新
黑格数 = 矩形和
若 ≥ k 且面积更小
更新答案
否则跳过
⚠️ 易错点
忘记无解输出 0
面积与和混淆
前缀和四个角写错
剪枝条件写反
03
样例手算推导
样例的逐个候选分析

🧮 样例:4 × 5 网格,k = 5,答案 6

00000
01111
00011
00011
1
先看能否用 5 个格子达成

面积 5 的矩形只有两种形状:

1 × 5(一行五列)或 5 × 1(五行一列)

但网格只有 4 行,所以 5 × 1 不可能

1 × 5 要求某一行全是黑格:

第 1 行 0 个、第 2 行 4 个、第 3 行 2 个、第 4 行 2 个

都不到 5 → 面积 5 不行

❌ 面积 5 不可行

2
再看面积 6 的形状

面积 6 可能是 2 × 3 或 3 × 2(或 1 × 6、6 × 1,网格放不下)

试 3 × 2:第 2~4 行、第 4~5 列

第 2 行后两格:1 1

第 3 行后两格:1 1

第 4 行后两格:1 1

共 6 个黑格 ≥ 5 ✅,面积 6

✅ 面积 6 可行,答案 ≤ 6

3
还有更小的吗?

面积已经试过 1 ~ 5 都不可行(面积 5 不可行,更小的当然也不行)

所以 6 就是最小值

✅ 答案 6

📊 候选汇总

面积可能的形状黑格数能达到 k = 5 吗
1 ~ 4更小的矩形否(黑格数 < 5)
51 × 5 / 5 × 1否(行内最多 4 个黑格)
62 × 3 / 3 × 2✅ 是(第 2~4 行第 4~5 列)

答案 6 ✓

🔑
注意"无解"的情况:如果整个网格的黑格总数都不到 k,那就不存在这样的子矩形,按要求输出 0。实现时可以先把答案初始化为 0,找到可行解再更新即可自然处理。

🧮 二维前缀和怎么用

二维前缀和 pre[i][j] 表示从 (1,1) 到 (i,j) 这个矩形内黑格的个数。

步骤公式说明
建表pre[i][j] = pre[i-1][j] + pre[i][j-1] − pre[i-1][j-1] + a[i][j]容斥原理:上 + 左 − 左上 + 自己
查询矩形 (r1,c1)~(r2,c2)pre[r2][c2] − pre[r1-1][c2] − pre[r2][c1-1] + pre[r1-1][c1-1]四个角做容斥
面积(r2 − r1 + 1) × (c2 − c1 + 1)行数 × 列数
⚠️
注意 pre 的下标从 1 开始:这样 pre[r1-1][...] 在 r1 = 1 时自然是 0,pre[0][*] 和 pre[*][0] 全为 0,不需要任何边界特判。这是二维前缀和的标准技巧。
04
解法对比
四重循环 + 前缀和 vs 滑动窗口

⚔️ 解法对比

🟢 四重循环 + 前缀和(推荐) 推荐

枚举四条边界,用前缀和 O(1) 查黑格数

  • 时间 O(n²m²)
  • n = m = 100 时约 2500 万
  • 每次查询 O(1)
  • 代码 25 行
💡
量级可行性:2500 万次循环,每次只做几次加法和比较,C++ 大约 0.1 ~ 0.3 秒,完全在时限内。

🟠 双指针滑动窗口

固定上下边界,让左右边界单调移动

  • 理论复杂度更低
  • 需要"黑格数单调"这个性质
  • 实现复杂、易错
  • 本题没必要
⚠️
为什么不容易做:固定上下边界后,随着右边界扩展黑格数确实单调增,但我们要的是"面积最小",需要枚举所有右边界再收缩左边界,虽然可行但实现繁琐。本题数据小,四重循环足够。

📈 性能对比

方案运算量(100 × 100)代码量
四重循环约 2.5 × 10⁷约 25 行
滑动窗口约 10⁴约 40 行
05
算法流程图
前缀和 + 枚举四条边界
开始读入 n、m、k 和网格;建立二维前缀和 preans = 0(无解时输出 0)枚举上边界 r1 和下边界 r2枚举左边界 c1 和右边界 c2黑格数 = 矩形和;面积 = 行数 × 列数黑格数 ≥ k,且面积比已知答案更小(或答案还是 0)吗?是 ✓ans = 面积否 ✗跳过输出 ans结束继续枚举边界组合
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

⬛ 最小黑格子矩形查找器

第一行输入 n、m、k,随后 n 行 01 串,程序会找出满足条件的最小矩形。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int pre[105][105];

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);

    // 建二维前缀和(下标从 1 开始)
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++) {
            int v = s[j - 1] - '0';
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + v;
        }
    }

    int ans = 0;                       // 0 表示暂无可行解

    for (int r1 = 1; r1 <= n; r1++)
        for (int r2 = r1; r2 <= n; r2++)
            for (int c1 = 1; c1 <= m; c1++)
                for (int c2 = c1; c2 <= m; c2++) {
                    // O(1) 求出矩形内黑格数
                    int ones = pre[r2][c2] - pre[r1-1][c2]
                             - pre[r2][c1-1] + pre[r1-1][c1-1];
                    if (ones < k) continue;

                    int area = (r2 - r1 + 1) * (c2 - c1 + 1);
                    if (ans == 0 || area < ans) ans = area;
                }

    printf("%d\n", ans);               // 无解时自然输出 0
    return 0;
}
🔑
为什么用 ans == 0 表示"暂无解"?因为题目规定"无解输出 0",而面积至少是 1,所以 0 可以安全地当作"尚未找到"的标记。这样更新条件写成 if (ans == 0 || area < ans),最后直接输出 ans 就同时满足了"有解输出最小值、无解输出 0"。

📖 关键几行怎么看

代码作用为什么这样写
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + v前缀和递推容斥原理
ones = pre[r2][c2] - pre[r1-1][c2] - pre[r2][c1-1] + pre[r1-1][c1-1]矩形内黑格数四个角的容斥,O(1) 完成
if (ones < k) continue;筛选黑格数不够直接跳过
if (ans == 0 || area < ans)更新最小值ans == 0 兼顾"首次找到"和"无解"两种情况
⚠️
三个坑:① 前缀和公式漏掉 + pre[r1-1][c1-1];② 把"黑格数"和"面积"混淆(黑格数 ≥ k 是条件,面积是目标);③ 忘记"无解输出 0"(用 ans 初值 0 可自然处理)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4 5 5
00000 / 01111 / 00011 / 00011
6题面样例
1 1 1
1
1单格黑格
1 1 1
0
0无解(没有黑格)
2 2 4
11 / 11
4k 等于总黑格数,必须取整个网格
3 3 3
111 / 000 / 000
3第一行三个黑格,取 1 × 3
2 3 5
111 / 011
5共 5 个黑格,整个 2 × 3 网格是唯一选择
✅
自查清单:① 前缀和四个角对吗?② 区分了黑格数和面积吗?③ 无解输出了 0 吗?

🚨 易错点清单

⚠️
前缀和公式错:必须是"上 + 左 − 左上",查询时是"右下 − 上 − 左 + 左上"。
⚠️
混淆黑格数与面积:条件是黑格数 ≥ k,要最小化的是面积。
⚠️
忘记无解输出 0:ans 初值取 0 可以自然处理。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n²m²)
空间复杂度
O(nm)
n, m 最大
100
最坏运算
约 2.5 × 10⁷

时间怎么算的?

空间都用在哪?

一个 (n+1) × (m+1) 的前缀和数组。

✅ 约 2500 万次操作,C++ 约 0.1 ~ 0.3 秒,可通过。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 二维前缀和模板(下标从 1 开始)
int pre[N][M], a[N][M];
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];

// 查询矩形和
int rectSum(int r1, int c1, int r2, int c2) {
    return pre[r2][c2] - pre[r1-1][c2] - pre[r2][c1-1] + pre[r1-1][c1-1];
}

// 剪枝思路(可以加,但本题不加也够快)
// 如果当前面积已经 >= 已知最优答案,就没必要继续(内层循环可提前 break)
// 因为固定 r1、c1 时,随 r2、c2 增大面积单调增

// "无解输出 0"的巧妙处理:把答案初值设为 0,更新条件加 ans == 0

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
二维前缀和O(1) 矩形查询子矩阵统计、区域计数、图像处理
枚举四条边界小规模网格的通用解法求最优子矩形类问题
用 0 当"无解标记"面积恒 ≥ 1所有"无解输出特定值"的题
🌟
思考题:如果 n、m 放大到 1000,四重循环的 10¹² 就超时了。该怎么优化?(提示:可以二分答案"边长"或"面积"——但更常用的思路是"固定上下边界 + 双指针左右边界",利用"右边界右移时黑格数单调增"这个性质把内层降到 O(m),整体 O(n²m)。这类"固定两维 + 单调性优化另外两维"是二维问题的常用降维套路。)