黑白方块 题解

题目分析

我们有一个 $n \times m$ 的网格，用 0 表示白色格子，1 表示黑色格子。
一个子矩形被称为平衡的，当且仅当它包含的黑色格子数量等于白色格子数量。

我们需要找到面积最大（即包含格子总数最多）的平衡子矩形，并输出该格子的数量。如果不存在任何平衡子矩形，则输出 0。

数据范围：$1 \le n, m \le 10$，规模非常小，可以使用较高复杂度的解法。

---

解题思路

因为 $n$ 和 $m$ 最大只有 $10$，我们可以直接枚举所有可能的子矩形。

具体做法：

1. 枚举子矩形的左上角坐标 $(i, j)$。
2. 枚举子矩形的右下角坐标 $(ii, jj)$，其中 $i \le ii \le n$，$j \le jj \le m$。
3. 对于当前的子矩形，统计其中 0 和 1 的个数。
4. 如果两者相等，计算该子矩形的面积 $(ii - i + 1) \times (jj - j + 1)$，并与当前最大值比较更新。
5. 遍历结束后输出最大值。

这种暴力方法的优点是思路简单，代码容易实现，在 $n,m \le 10$ 时完全可行。

---

算法说明

使用四重循环枚举所有子矩形：

cpp
复制
1for (int i = 1; i <= n; i++)            // 左上角行号
2    for (int j = 1; j <= m; j++)        // 左上角列号
3        for (int ii = i; ii <= n; ii++) // 右下角行号
4            for (int jj = j; jj <= m; jj++) // 右下角列号
5                // 检查子矩形 (i,j) ~ (ii,jj) 是否平衡

检查函数 check(xa, ya, xb, yb) 遍历子矩形中所有格子，统计 0 和 1 的数量，返回它们是否相等。

边界条件：如果没有任何平衡子矩形，ans 保持初始值 0，正确输出 0。

优化小提示：
虽然本题不需要，但若数据范围更大，可以用二维前缀和分别预处理 0 和 1 的数量，将检查环节优化到 $O(1)$，总复杂度降至 $O(n^2 m^2)$。

---

时间复杂度分析

• 枚举所有子矩形：一共有 $O(n^2 m^2)$ 个可能的子矩形。
• 每次 check 需要遍历子矩形内所有格子，最坏情况为 $O(nm)$。
• 总时间复杂度为 $O(n^3 m^3)$。

当 $n, m \le 10$ 时，最大计算量约为 $10^6$ 级别，在时间限制内可以轻松通过。

---

参考代码与解释

cpp
复制
1#include<bits/stdc++.h>
2using namespace std;
3const int N = 55;     // 预留足够空间（题目要求 ≤10，这里开了 55）
4int w[N][N];
5int n, m;
6
7// 检查以 (xa,ya) 为左上角、(xb,yb) 为右下角的子矩形是否平衡
8bool check(int xa, int ya, int xb, int yb) {
9    int a[2] = {0, 0};  // a[0] 统计白色，a[1] 统计黑色
10    for (int i = xa; i <= xb; i++) {
11        for (int j = ya; j <= yb; j++) {
12            a[w[i][j]]++;
13        }
14    }
15    return a[0] == a[1]; // 数量相等则平衡
16}
17
18int main() {
19    cin >> n >> m;
20    // 读入网格，字符转换为数字存入 w 数组
21    for (int i = 1; i <= n; i++) {
22        string s;
23        cin >> s;
24        for (int j = 1; j <= m; j++) {
25            w[i][j] = s[j-1] - '0';
26        }
27    }
28
29    int ans = 0;
30    // 枚举所有子矩形
31    for (int i = 1; i <= n; i++) {
32        for (int j = 1; j <= m; j++) {
33            for (int ii = i; ii <= n; ii++) {
34                for (int jj = j; jj <= m; jj++) {
35                    if (check(i, j, ii, jj)) {
36                        int area = (ii - i + 1) * (jj - j + 1);
37                        ans = max(ans, area);
38                    }
39                }
40            }
41        }
42    }
43    cout << ans << "\n";
44    return 0;
45}

代码说明：

• w[i][j] 存储格子颜色（0 或 1），方便在 check 中直接作为下标使用。
• a[0] 和 a[1] 分别记录白色和黑色出现的次数，最后判断是否相等。
• 主循环中，左上角 (i,j) 和右下角 (ii,jj) 构成一个合法子矩形，调用 check 判断，并更新最大面积。

---

总结

本题考察了对二维数组子矩形的枚举和简单统计。由于数据规模极小，直接暴力即可。
同学们可以借本题练习前缀和优化，思考当 $n,m$ 扩大到几百时该如何提速。