P10719 [GESP202406 五级] 黑白格 二维前缀和

P10719 [GESP202406 五级] 黑白格
用二维前缀和存下来在从起点到ij结束这个矩形内一共有多少个1。
先用4个for循环枚举这个矩形的 左上角的横纵坐标（x1,y1） 以及 右下角的横纵坐标(x2,y2) 。
(x2-x1+1) * (y2-y1+1)表示这里面有多少个格子。
用前缀和快速的求出子矩形这个范围内有多少个1。

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N],sum[N][N];
int n,m,k;
int main()
{cin>>n>>m>>k;for(int i = 1 ; i <= n ; ++i)for(int j = 1 ; j <= m ; ++j){char ch;cin>>ch;sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];if(ch == '1')sum[i][j]++;}int ans = m*n+1;for(int x1 = 1 ; x1 <= n ; ++x1)for(int x2 = x1 ; x2 <= n ; ++x2)for(int y1 = 1 ; y1 <= m ; ++y1)for(int y2 = y1 ; y2 <= m ; ++y2){int now = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];if(now >= k)ans = min(ans,(x2-x1+1) * (y2-y1+1));}if(ans == m*n+1)cout<<"0\n";elsecout<<ans<<endl;return 0;
}