[GESP202406 四级] 黑白方块

题目传送门

B4005 [GESP202406 四级] 黑白方块

题目描述

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

输入格式

第一行包含两个正整数 $n,m$，含义如题面所示。

之后 $n$ 行，每行一个长度为 $m$ 的 $01$ 串，代表网格图第 $i$ 行格子的颜色，如果为 $0$，则对应格子为白色，否则为黑色。

输出格式

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

样例输入 #1

4 5
00000
01111
00011
00011

样例输出 #1

16

提示

【样例解释】

对于样例 $1$，假设 $(i,j)$ 代表第 $i$ 行第 $j$ 列，最大的平衡子矩形的四个顶点分别为 $(1,2),(1,5),(4,2),(4,5)$。

【数据范围】

对于全部数据，保证有 $1\le n,m\le 10$。

知识点：前缀和

‌前缀和‌是一个在计算机科学中常用的概念，主要用于降低查询时的时间复杂度。前缀和是一种预处理技术，通过对数组或矩阵进行一次遍历，计算出每个位置之前（包括该位置）的所有元素之和，存储在一个新的数组或矩阵中。这样，在进行多次区间查询时，可以直接通过前缀和数组或矩阵来快速获取结果，而不需要每次都重新计算区间内的元素和‌，可以将每次查询的时间复杂度从 O(N) 或者O(N^2)降低到 O(1)，其中 N 是区间的大小‌1。

常用前缀和：

‌一维前缀和‌：对于给定的一维数组，前缀和数组中的每个元素表示原数组中从第一个元素到当前元素的所有元素之和。例如，对于数组 [1, 2, 3, 4]，其前缀和数组为 [1, 3, 6, 10]。
‌二维前缀和‌：对于给定的二维数组，前缀和矩阵中的每个元素表示原二维数组中从左上角到当前位置的元素之和。例如，对于二维数组 [[1, 2], [3, 4]]，其前缀和矩阵为 [[1, 3], [6, 7]]‌1。

前缀和的实现方法：求前缀和用的是动态规划的思想

步骤如下：
‌初始化‌：创建一个新的数组或矩阵，用于存储前缀和。为了统一处理，通常下标0的位置元素不使用，直接置为0。
‌遍历‌：遍历原数组，对于每个位置 i，将前 i 个元素的和存储在前缀和数组的第 i 个位置，计算方法：prefix[i] = prefix[i-1]+arr[i]。矩阵的话，对于位置(i, j), 将左上角(1, 1)到(i, j)位置的元素之和存储在前缀和矩阵的(i, j)位置，计算方法：prefix[i][j] = prefix[i][j-1]+prefix[i-1][j]-prefix[i-1][j-1]+arr[i][j]。
‌查询‌：对于任意区间 [L, R]，查询结果可以通过前缀和数组直接计算得到：sum(L, R) = prefix[R] - prefix[L-1]‌。矩阵，对于任意区间[x1, y1, x2, y2]，查询结果可以通过前缀和矩阵直接计算得到：sum(x1, y1, x2, y2) = prefix[x2][y2]-prefix[x2][y1-1]-prefix[x1-1][y2]+prefix[x1-1][y1-1]。

#include<bits/stdc++.h>
using namespace std;
int n, m, arr[11][11], sum[11][11];
char ch;
int main() {cin>>n>>m;for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){cin>>ch;arr[i][j]=ch-'0';sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+arr[i][j];}}int res=0;for(int x1=1; x1<=n; x1++){for(int y1=1; y1<=m; y1++){for(int x2=x1; x2<=n; x2++){for(int y2=y1; y2<=m; y2++){int num = sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];if(2*num == (x2-x1+1)*(y2-y1+1)){if(2*num > res) res=2*num;}}}}}cout<<res;return 0;
}