题目
题目描述
小杨有一个 𝑛 行 𝑚 列的网格图，其中每个格子要么是白色，要么是黑色。对于网格图中的一个子矩形，小杨认为它是平衡的当且仅当其中黑色格子与白色格子数量相同。小杨想知道最大的平衡子矩形包含了多少个格子。
输入格式
第一行包含两个正整数 𝑛，含义如题面所示。
之后 𝑛 行，每行一个长度为 𝑚 的 01 串，代表网格图第 𝑖 行格子的颜色，如果为 0，则对应格子为白色，否则为黑色。
输出格式
输出一个整数，代表最大的平衡子矩形包含格子的数量，如果不存在则输出 0。
输入样例
4 5
00000
01111
00011
00011
输出样例
16
数据范围
对于全部数据，保证有 1≤𝑛,𝑚≤101≤n,m≤10。
题目解析
首先我们要知道这道题他主要再问我们什么
子问题1： 如何判断一个矩形是平衡的
遍历这个矩形的每个点，分别记录出来黑色和白色的数量，判断是否相等--》 O(n^2)
子问题2： 如何取出来一个子矩形
确定一个矩形，需要哪些内容？
- 知道方块对角两个点，便可以确定一个矩形
- 起始行 xa、终止行xb、起始列ya、终止列yb --》 O(n^4)
总时间复杂度：O(n^6)
代码编写
# include <bits/stdc++.h>
using namespace std;
const int N = 55;
int w[N][N];
int n, m;
// **1.定义函数check**
//1定义一个函数，获取对角两个点的xy坐标，用于检查指定矩形区域内的黑白两类元素数量是否相等
bool check(int xa, int ya, int xb, int yb){
// 初始化一个大小为2的数组，用于统计黑白两类元素的数量
int a[2] = {0, 0};
// 遍历指定矩形区域内的所有元素
for (int i = xa; i <= xb; i++){
for (int j = ya; j <= yb; j++){
// 根据当前元素值作为索引，递增对应的计数器
a[w[i][j]]++;
}
}
// 判断两类元素数量是否相等
return a[0] == a[1];
}
int main(){
//**2.读取输入**
// 读取输入的两个整数 行数【n】 和 列数【m】
cin >> n >> m;
// 读取 n 行字符串，并将其转换为二维数组 w
for (int i = 1; i <= n; i++){
string s;
cin >> s;
// 遍历字符串中的每个字符
for (int j = 1; j <= m; j++){
// 将字符转换为数字（'0' 或 '1'）并存储在二维数组 w 中、
// 字符串 s 的第 j-1 个字符减去字符 '0' 可以得到对应的整数值 0 或 1
w[i][j] = s[j-1] - '0';
}
}
// 初始化答案变量 ans 为 0，用于记录最大子矩阵的面积
int ans = 0;
//**3.遍历所有可能的子矩阵**
// 枚举所有可能的子矩阵的左上角坐标 (xa, ya) 和右下角坐标 (xb, yb)
for (int xa = 1; xa <= n; xa++) {
for (int ya = 1; ya <= m; ya++) {
for (int xb = xa; xb <= n; xb++) {
for (int yb = ya; yb <= m; yb++) {
// 调用 check 函数检查子矩阵 (xa, ya) 到 (xb, yb) 是否满足条件
if (check(xa, ya, xb, yb)) {
// 计算子矩阵的面积
// 子矩阵的高度为 xb-xa+1，宽度为 yb-ya+1
// 面积为高度乘以宽度
int area = (xb - xa + 1) * (yb - ya + 1);
// 更新最大面积 ans
// 如果当前子矩阵的面积大于之前的最大面积，则更新 ans
ans = max(ans, area);
}
}
}
}
}
// 输出最大面积
cout << ans << endl;
return 0;
}
image.png
