【每日一题】「土」秘法地震

题意

求矩形区域中长度为k的正方形中含有1的正方形个数。

solution

枚举正方形只需要确定对角两个点即可，然后用二维前缀和维护 [0,0]-[i,j]含有1的个数，枚举正方形区域时二维前缀和查询该区域1的个数是否da即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, k, res, sum[N][N];
char s[N][N];
int main() {
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) cin >> s[i] + 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      sum[i][j] =
          sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (s[i][j] == '1');
  for (int i = 1; i + k - 1 <= n; i++) {
    for (int j = 1; j + k - 1 <= m; j++) {
      int x = i + k - 1, y = j + k - 1;
      if (sum[x][y] - sum[i - 1][y] - sum[x][j - 1] + sum[i - 1][j - 1]) res++;
    }
  }
  cout << res << '\n';
  return 0;
}