4628: 【GESP2406四级】黑白方块

内存限制：64 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

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

输入

第一行包含两个正整数$n,m$ ，含义如题面所示。
之后$n$ 行，每行一个长度为$m$ 的$01$ 串，代表网格图第$i$ 行格子的颜色，如果为$0$ ，则对应格子为白色，否则为黑色。

输出

输出一个整数，代表最大的平衡子矩形包含格子的数量，如果不存在则输出$0$ 。

样例输入 复制 

4 5
00000
01111
00011
00011

样例输出 复制 

16

提示

#include<bits/stdc++.h>
using namespace std;
const int N = 55;
int w[N][N];
int n, m;
bool check(int xa, int ya, int xb, int yb) {
    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() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++) {
            w[i][j] = s[j - 1] - '0';
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int ii = i; ii <= n; ii++) {
                for (int jj = j; jj <= m; jj++) {
                    if (check(i, j, ii, jj)) {
                        ans = max(ans, (ii - i + 1) * (jj - j + 1));
                    }
                }
            }
        }
    }
    cout << ans << "\n";
}

来源/分类

提交提交记录统计露一手!