题目

题目描述
小杨有一个 𝑛 行 𝑚 列的网格图，其中每个格子要么是白色，要么是黑色。对于网格图中的一个子矩形，小杨认为它是平衡的当且仅当其中黑色格子与白色格子数量相同。小杨想知道最大的平衡子矩形包含了多少个格子。

输入格式
第一行包含两个正整数 𝑛，含义如题面所示。

之后 𝑛 行，每行一个长度为 𝑚 的 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