solution
因为地震的区域是固定的。所以枚举一下地震矩形的右下角,然后判断一下这个矩形内是不是含有1就行了。
怎么判断一个矩形内是不是有1?二维前缀和一下,然后计算一下查询矩阵得和是不是比0大就行了。
code
/* * @Author: wxyww * @Date: 2020-05-17 15:40:13 * @Last Modified time: 2020-05-17 16:19:51 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cmath> using namespace std; typedef long long ll; const int N = 1010; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } char s[N]; int a[N][N],k,n,m; int main() { n = read(),m = read(),k = read(); for(int i = 1;i <= n;++i) { scanf("%s",s + 1); for(int j = 1;j <= m;++j) { a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + s[j] - '0'; // printf("%d ",a[i][j]); } // puts(""); } int ans = 0; for(int i = k;i <= n;++i) { for(int j = k;j <= m;++j) { int x1 = i - k + 1,y1 = j - k + 1; if(a[i][j] - a[i][y1 - 1] - a[x1 - 1][j] + a[x1 - 1][y1 - 1]) ans++; } } cout<<ans; return 0; }