题意
解析
我写的朴素的二维前缀和,这样比较麻烦
可以这样,
f1[i][j]代表当前行第一个到第j个的前缀和 f1[i][j]=f1[i][j-1]+a[i][j]
f2[i][j]代表当前列第一个到第i个的前缀和 f2[i][j]=f2[i-1][j]+a[i][j]
判断f1[i][j],f2[i][j],f1[i][m]-f1[i][j],f2[n][j]-f2[i][j]即可
代码
//从(1,1)开始的前缀和
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N][N],f[N][N];
int n,m;
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
f[i][j] = a[i][j] + f[i-1][j] + f[i][j-1] - f[i-1][j-1];
}
}
int cnt = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]) continue;
if(f[i-1][j] - f[i-1][j-1] > 0) cnt++;
if(f[i][j-1] - f[i-1][j-1] > 0) cnt++;
if(f[i][m] - f[i][j] - f[i-1][m] + f[i-1][j] > 0) cnt++;
if(f[n][j] - f[n][j-1] - f[i][j] + f[i][j-1] > 0) cnt++;
}
}
cout << cnt;
return 0;
}
标签:f1,f2,CF729B,前缀,int,1200,++,cnt
From: https://www.cnblogs.com/dtdbm/p/17127177.html