题解:这个题先进行二维前缀和预处理,然后枚举一遍所有情况的左上角的点,统计符合条件的个数。关于这个二维前缀和,就像在一个矩形里求其中一个小矩形面积。通过 sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + num[i][j] 计算二维前缀和,然后就是注意枚举k*k区域时的情况怎么写(详情看代码QAQ)。
// .--------------. // | Try First One| // '--------------' // | .--------------. // | | | // V V | // .--------------. | // | AC. |<---. | // '--------------' | | // (True)| |(False) | | // .--------' | | | // | V | | // | .--------------. | | // | | Try Again |----' | // | '--------------' | // | | // | .--------------. | // '->| Try Next One |-------' // '--------------' #include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <string> #include <cstring> using namespace std; const long long N = 1e10 + 7; const int maxn = 1e3 + 5; const long long INF = 8e18; typedef long long ll; #define for0(i,n) for(int i = 0;i < n;i++) #define for1(i,n) for(int i = 1;i <= n;i++) int sum[maxn][maxn],num[maxn][maxn]; int main() { int n ,m, k, total = 0; cin >> n >> m >> k; for1(i,n) for1(j,m){ char m; cin >> m; if(m == '1') num[i][j] = 1; sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + num[i][j]; } for1(i,n+1-k) for1(j,m+1-k){ int ii = i+k-1,jj = j+k-1; if(sum[ii][jj] - sum[ii][j-1] - sum[i-1][jj] + sum[i-1][j-1]) total++; } cout << total << endl; return 0; }