洛谷 P10719 \\[GESP202406 五级] 黑白格——暴力美学与图像处理的最小外接矩形

洛谷 P10719 [GESP202406 五级] 黑白格——暴力美学与图像处理的最小外接矩形

📌 摘要

P10719 给定一个 n×m 的 01 网格，找至少包含 k 个黑格的最小子矩形面积。n,m≤100，暴力枚举所有矩形 O(n²×m²) 可以通过。本文分析了暴力解法的设计思路——从左上角出发，逐步扩展宽度和高度，遇到满足条件的就记录面积并跳出——并延伸到二值图像处理中的最小外接矩形（Minimum Bounding Rectangle），从 1970 年代卫星遥感到现代目标检测 YOLO 的 bounding box，核心操作都是同一个：在二值网格上找一个满足条件的最小矩形。

题目链接：P10719 黑白格

📚 目录

• 📝 前言

• 🔍 题目在考什么

• 💡 思路

• 📝 伪代码

• 🎯 关键点

• ⚠️ 注意事项

• 🌳 延伸：从黑白格到目标检测——最小外接矩形的故事

  • 🖼️ 二值图像：最简单的图像

  • 📐 最小外接矩形：1970 年代的卫星眼睛

  • 🔍 目标检测：从滑动窗口到 YOLO

  • 📊 前缀和：从暴力到高效

  • 🗺️ 地理信息系统：栅格数据无处不在

• 📚 延伸阅读文献

📝 前言

这篇题解没有源代码，只有伪代码。

作为一名信奥教练，我不提倡复制粘贴。我见过太多学生搜到题解、复制、粘贴、提交、AC——代码跑通了，脑子没跑通。下次遇到变体题，还是不会。

伪代码剥掉了语言的壳，只留算法的骨架。你看不到 #include，看不到 cin、cout，看不到那些让你以为"我会了"的语法细节。你能看到的只有：这一步做什么、下一步做什么、为什么这么做。

如果你是路过的友友，已经在这道题上挣扎了很久——先去喝杯水，回来重新看看自己卡在哪一步。是没读懂题意？是思路方向偏了？还是代码有 bug 但逻辑其实对？大多数时候不是不会，是走偏了。偏了不可怕，可怕的是偏了之后直接放弃，去抄一份能 AC 的代码。抄完你以为你懂了，其实你只是搬了别人的结论。

除非你时间真的紧张——比赛临近、作业要交——那种情况先 AC 再说，能理解。但平时练习，给自己一点耐心。先自己想、自己写、自己调，跑不过了再来看伪代码：你的思路和这里差在哪一步。那一步，就是你真正学到的东西。

🔍 题目在考什么

给定 n×m 的 01 网格（0=白，1=黑），找至少包含 k 个 1 的最小面积子矩形。

n,m≤100 意味着：矩形数量最多 C(100,2)×C(100,2) ≈ 2.5×10⁷ 个，暴力枚举所有矩形在 1 秒内可行。

核心是矩形枚举 + 计数：怎么遍历所有可能的矩形，怎么高效计算每个矩形内 1 的个数。

💡 思路

暴力做法：枚举所有子矩形的左上角 (y, x) 和宽高，逐个扫描矩形内的格子数 1 的个数，满足 ≥k 就记录面积，取最小值。

原始代码的枚举策略比较特别——不是标准的"四重循环枚举左上右下"，而是渐进扩展宽度：

这个策略的特点是宽度优先扩展——对每个起始位置，先试窄矩形（宽度 1），不够就加宽，找到第一个满足条件的就记录。因为面积 = 宽×高，窄矩形如果行数少，面积可能更小，所以先试窄的有道理。

更标准的暴力写法：四重循环枚举左上角 (r1,c1) 和右下角 (r2,c2)，对每个矩形数 1 的个数。复杂度 O(n²×m²×nm)——太慢。加上前缀和优化到 O(n²×m²)——可行。

📝 伪代码

原始代码的暴力版本（渐进扩展宽度）：

读取 n, m, k
读取网格 grid[0..n-1][0..m-1] // 每行是一个 01 串
最小面积 = n*m + 1 // 初始化为不可能的大值

对 y = 0 到 n-1: // 起始行
宽度 = 1 // 从宽度 1 开始
对 x = 0 到 m-1: // 起始列
计数 = 0
对 行 = y 到 n-1: // 逐行向下扩展
对 列 = x 到 x+宽度-1: // 扫描当前行的宽度范围
如果 grid[行][列] == '1':
计数++
如果 计数 >= k: // 满足条件
面积 = 宽度 × (行 – y + 1)
如果 面积 < 最小面积:
最小面积 = 面积
跳出行循环 // 找到了就停，加宽没意义

// 扩展宽度，重试同一 x
如果 宽度 < m – x:
宽度++
x– // 让 for 循环不前进，重试同一 x
如果 宽度 >= m – x: // 到达右边界
宽度 = 1 // 重置宽度

如果 最小面积 == n*m + 1:
输出 0 // 无解
否则:
输出 最小面积

标准暴力 + 前缀和版本（O(n²×m²)）：

读取 n, m, k
读取网格 grid[0..n-1][0..m-1]

// 预处理二维前缀和
前缀和 pre[i][j] = 矩形 (0,0) 到 (i-1,j-1) 内 1 的个数
pre[i][j] = pre[i-1][j] + pre[i][j-1] – pre[i-1][j-1] + (grid[i-1][j-1]=='1')

最小面积 = n*m + 1

// 枚举所有子矩形
对 r1 = 0 到 n-1: // 上边界
对 r2 = r1 到 n-1: // 下边界
对 c1 = 0 到 m-1: // 左边界
对 c2 = c1 到 m-1: // 右边界
// O(1) 计算矩形内 1 的个数
计数 = pre[r2+1][c2+1] – pre[r1][c2+1] – pre[r2+1][c1] + pre[r1][c1]
如果 计数 >= k:
面积 = (r2-r1+1) × (c2-c1+1)
如果 面积 < 最小面积:
最小面积 = 面积

输出 最小面积（如果仍为 n*m+1 则输出 0）

🎯 关键点

⚠️ 最常见的误解：矩形不需要全是 1。 题目说"至少包含 k 个黑色格子"——意思是矩形内 1 的个数 ≥ k 就行，允许夹杂 0。但很多人下意识理解成"矩形必须全部是 1"，于是去找纯黑矩形。更糟的是，样例的矩形恰好全是 1（6 个格子 6 个 1），加深了这个误解。

实际上，如果一个 2×3 矩形里有 5 个 1 和 1 个 0，面积 6、含 5 个 1 ≥ k=5，它同样合法。甚至可能比纯黑矩形更优——因为纯黑矩形可能需要更大的面积才能凑够 k 个 1。

正确理解：矩形内 1 的个数 ≥ k，不管 0 有几个。

"渐进扩展宽度"的设计思路。 原始代码不是朴素地枚举所有矩形，而是对每个起始位置，从宽度 1 开始逐步加宽。找到满足条件的就记录面积并跳出——因为继续加宽只会让面积更大。这是一种贪心剪枝：窄矩形如果已经满足条件，就不需要试更宽的。

为什么要 x–。 当宽度从 end_x 扩展到 end_x+1 时，需要重新从同一列 x 开始扫描。但 for 循环的 x++ 会跳到下一列，所以用 x– 抵消，让下一轮循环仍然处理同一 x。这是一个常见的"手动控制循环变量"技巧。

前缀和的威力。 标准暴力每次数矩形内 1 的个数要 O(n×m)，总共 O(n²×m²×nm) = O(10¹⁰)，太慢。前缀和把"数 1 的个数"从 O(n×m) 降到 O(1)，总共 O(n²×m²) = O(10⁸)，1 秒内能过。

用样例追踪（n=4, m=5, k=5）：

00000
01111
00011
00011

最优矩形：第 2-4 行（0 基下标 1-3），第 4-5 列（0 基下标 3-4），面积 2×3=6，含 6 个 1 ≥ 5。

最小面积：6。

⚠️ 注意事项

• 暴力能过但有风险。 n,m=100 时，矩形数量约 2.5×10⁷ 个。如果每个矩形都 O(n×m) 扫描，总共 O(10¹⁰)，会超时。原始代码的渐进扩展有剪枝效果，但最坏情况仍可能慢。加前缀和是更稳妥的做法。

• int 溢出。 n,m=100，k≤10⁴，面积最大 10⁴，int 范围足够。但如果用前缀和，累加 1 的个数最多 10⁴，也在 int 范围内。

• VLA 问题。 string str01[n] 是变长数组，不是标准 C++。可用 vector<string> 或固定大小数组替代。

• 无解情况。 如果网格中 1 的总数 < k，没有任何矩形满足条件，应输出 0。原始代码用 min_area = n*m+1 初始化，最后检查是否仍为此值来判断无解——正确。

• 宽度重置时机。 end_x 在到达右边界（end_x >= m-x）时重置为 1。如果重置逻辑有误，可能漏掉某些矩形或重复扫描。

• x– 的边界。 当 x=0 时 x– 变成 -1，但下一轮 for 循环 x++ 变回 0，不会有问题。但如果 x 已经在边界，x– 可能让循环多跑一轮——需要确认逻辑正确。

🌳 延伸：从黑白格到目标检测——最小外接矩形的故事

你在 P10719 里做的事——在二值网格上找一个包含足够多"目标"的最小矩形——在计算机视觉里有一个正式名字：最小外接矩形（Minimum Bounding Rectangle, MBR）。这个操作从 1970 年代的卫星遥感到今天的目标检测，无处不在。

🖼️ 二值图像：最简单的图像

你的 01 网格就是一张二值图像（Binary Image）——每个像素只有两种值：黑（1）或白（0）。这是图像处理中最基础的表示形式（Binary Image — Wikipedia）。

二值图像的历史比计算机还早：1900 年代初的电报传真就是二值传输——“有信号=黑，无信号=白”。1960 年代第一台扫描仪把照片转成数字网格时，第一步就是二值化：设定一个阈值，比阈值暗的标 1（黑），比阈值亮的标 0（白）（Image Thresholding — OpenCV）。

你在 P10719 里输入的 00000 / 01111 / 00011 / 00011，和卫星图、医学切片、文档扫描的二值化结果在数学上完全一样——一个 n×m 的 0/1 矩阵。

📐 最小外接矩形：1970 年代的卫星眼睛

1972 年，美国发射 Landsat-1 卫星，传回地球表面的数字图像。分析师面对的是 185km×185km 的多光谱图像，需要从中提取有用信息——森林面积、城市边界、农作物分布（Landsat Program — NASA）。

他们的第一步操作就是：把多光谱图像二值化（你的 01 网格），然后找目标区域的最小外接矩形。比如把植被指数 > 0.3 的像素标 1（是植被），其余标 0，然后找包含足够多 1 的最小矩形——这就是你在 P10719 里做的事。

1970 年代美国地质调查局（USGS）开发的 GIS 系统里，最小外接矩形是最基本的几何操作之一——它把不规则的像素块压缩成一个矩形，用四个数字（xmin, ymin, xmax, ymax）代替成千上万个像素坐标（GIS — Wikipedia）。

🔍 目标检测：从滑动窗口到 YOLO

在计算机视觉中，"在图像里找包含目标的矩形"就是目标检测（Object Detection）的核心任务。你的 P10719 是它的最简化版本（Object Detection — Wikipedia）。

2001 年——Viola-Jones 人脸检测器。 Paul Viola 和 Michael Jones 发表了实时人脸检测算法。核心思想：在图像上滑动一个矩形窗口，对每个窗口判断"是不是人脸"。窗口从小到大逐级扫描——和你从宽度 1 逐步扩展的思路异曲同工（Viola-Jones — Wikipedia）。

积分图（Integral Image） 是 Viola-Jones 的关键加速——它就是你在前缀和版本里用的二维前缀和。任何一个矩形内的像素和可以在 O(1) 时间内算出来，不需要逐个扫描。Viola 和 Jones 的贡献正是把这个技巧用在了实时检测上（Viola-Jones — Wikipedia）。

2012 年——深度学习时代。 AlexNet 在 ImageNet 上的突破让卷积神经网络（CNN）成为图像识别的标准。R-CNN（2014）用 CNN 对每个候选矩形分类，YOLO（2016）把整个检测变成单次前向传播[（YOLO — Wikipedia）](https://en.wikipedia.org/wiki/YOLO_(algorithm)）。

YOLO 不再枚举所有矩形——它直接从图像预测"哪里有矩形"。但底层逻辑没变：在二值网格上找满足条件的最小矩形。你的 P10719 暴力解法是 YOLO 的远古祖先——区别只是 YOLO 用神经网络学会了"哪些位置值得看"，而你老实地看遍了所有位置。

📊 前缀和：从暴力到高效

你在伪代码里看到的两种版本——暴力逐格扫描 O(n×m) 和前缀和 O(1)——对应了两种工业级算法：

二维前缀和 = 积分图。 这个等价关系是 2001 年 Viola-Jones 论文的核心贡献之一。他们在不知道"前缀和"这个名字的情况下，独立提出了完全相同的数学结构，命名为"Integral Image"（Viola-Jones — Wikipedia）。你在洛谷上用的前缀和技巧，和 2001 年让实时人脸检测成为可能的积分图，是同一个数学工具。

🗺️ 地理信息系统：栅格数据无处不在

你的 01 网格在 GIS 中叫栅格数据（Raster Data）。每一格代表一块地面的属性：是/不是森林、是/不是水体、是/不是建筑（Raster Data — GIS Wiki）。

USGS 3DEP（3D Elevation Program）提供全美 1 米分辨率的数字高程模型——一张图就是 10⁸ 个格子。在这些数据上找"海拔 > 某值的连续区域的最小外接矩形"，就是你 P10719 的工业版（USGS 3DEP — USGS）。

你的 for 循环遍历 n×m 的网格，和 ArcGIS、QGIS 在处理卫星数据时做的事一模一样——只是你的网格 100×100，它们的网格 10⁴×10⁴。

📚 延伸阅读文献

论文与技术文档

在线资源

推荐教材

• R. C. Gonzalez, R. E. Woods. Digital Image Processing (4th Edition). Pearson, 2018. —— 图像处理圣经，含二值图像、连通域、外接矩形。

• R. Szeliski. Computer Vision: Algorithms and Applications (2nd Edition). Springer, 2022. —— 计算机视觉教材，含目标检测和滑动窗口。

• M. A. Zevenbergen, J. P. Wilson. Geographic Information Systems and Science. Wiley, 2020. —— GIS 教材，含栅格数据处理。

本文标签：#算法 #暴力枚举 #前缀和 #二值图像 #最小外接矩形 #目标检测 #YOLO #GIS #洛谷题解 #信奥 #GESP #C++ #五级

本文首发于 CSDN，作者：HugoStudio_SWAN