求至少包含 k 个黑格的最小子矩形面积,无解输出 0。
给定 n 行 m 列的 01 网格(0 白、1 黑)。求至少包含 k 个黑色格子的子矩形中,包含格子总数的最小值;若不存在则输出 0。
例:4 × 5 网格、k = 5 时,最小子矩形是第 2~4 行、第 4~5 列,共 6 个格子(其中 6 个黑格)。
二维前缀和枚举矩形边界最小面积可行性
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、m、k;随后 n 行 01 串 |
| 输出 | 最小子矩形的格子数,无解输出 0 |
| 数据范围 | 1 ≤ n, m ≤ 100 |
| k 的范围 | 1 ≤ k ≤ n × m |
| 目标 | 黑格数 ≥ k 且面积最小 |
00000 01111 00011 00011
面积 5 的矩形只有两种形状:
1 × 5(一行五列)或 5 × 1(五行一列)
但网格只有 4 行,所以 5 × 1 不可能
1 × 5 要求某一行全是黑格:
第 1 行 0 个、第 2 行 4 个、第 3 行 2 个、第 4 行 2 个
都不到 5 → 面积 5 不行
❌ 面积 5 不可行
面积 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
面积已经试过 1 ~ 5 都不可行(面积 5 不可行,更小的当然也不行)
所以 6 就是最小值
✅ 答案 6
| 面积 | 可能的形状 | 黑格数能达到 k = 5 吗 |
|---|---|---|
| 1 ~ 4 | 更小的矩形 | 否(黑格数 < 5) |
| 5 | 1 × 5 / 5 × 1 | 否(行内最多 4 个黑格) |
| 6 | 2 × 3 / 3 × 2 | ✅ 是(第 2~4 行第 4~5 列) |
答案 6 ✓
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,不需要任何边界特判。这是二维前缀和的标准技巧。枚举四条边界,用前缀和 O(1) 查黑格数
固定上下边界,让左右边界单调移动
| 方案 | 运算量(100 × 100) | 代码量 |
|---|---|---|
| 四重循环 | 约 2.5 × 10⁷ | 约 25 行 |
| 滑动窗口 | 约 10⁴ | 约 40 行 |
第一行输入 n、m、k,随后 n 行 01 串,程序会找出满足条件的最小矩形。
点按钮开始 →
#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 可自然处理)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 5 5 | 6 | 题面样例 |
1 1 1 | 1 | 单格黑格 |
1 1 1 | 0 | 无解(没有黑格) |
2 2 4 | 4 | k 等于总黑格数,必须取整个网格 |
3 3 3 | 3 | 第一行三个黑格,取 1 × 3 |
2 3 5 | 5 | 共 5 个黑格,整个 2 × 3 网格是唯一选择 |
一个 (n+1) × (m+1) 的前缀和数组。
✅ 约 2500 万次操作,C++ 约 0.1 ~ 0.3 秒,可通过。
// 二维前缀和模板(下标从 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 | 所有"无解输出特定值"的题 |