题目:
给一个nm的01矩阵。问有多少个kk的含1矩阵。(n最大1000)
做法:
二维前缀和。跟板子没啥区别。。
利用二维前缀和可以快速得到某矩形区域中数字的和。那么枚举所有k*k矩阵的右下角位置,利用二维前缀和得到矩阵中1的数量,大于零则ans++即可。
代码:
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ": " << a << endl using namespace std; typedef long long ll; const int N = 1010; char s[N]; int prefix[N][N]; int main(void){ IOS; int n, m, k; cin >> n >> m >> k; for (int i = 1; i <= n; ++i){ cin >> (s+1); for (int j = 1; j <= m; ++j){ if (s[j] == '1'){ prefix[i][j] = 1; } } } for (int i = 1; i <= n; ++i){ for (int j = 1; j <= m; ++j){ prefix[i][j] += prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]; } } int ans = 0; for (int i = k; i <= n; ++i){ for (int j = k; j <= m; ++j){ int cnt = prefix[i][j]-prefix[i][j-k]-prefix[i-k][j]+prefix[i-k][j-k]; if (cnt) ans++; } } cout << ans << endl; return 0; }