代码:
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a, b, s, x;
int A[3005][3005];
char S[3005];
int f1[3005][3005];
int f2[3005][3005];
int f3[3005][3005];
int g[3005][3005];
int g1 (int w, int h) {
if (w * h < s) return 0;
if (w + h < x) return 0;
return 1;
}
int main () {
scanf("%d%d%d%d%d%d", &n, &m, &a, &b, &s, &x);
for (int i = 1; i <= n; i++) {
scanf("%s", S);
for (int j = 0; j < strlen(S); j++)
A[i][j + 1] = S[j] - '0';
}
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++)
// printf("%d ", A[i][j]);
// puts("");
// }
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (A[i][j] == 0) continue;
else f1[i][j] = f1[i][j - 1] + 1;
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++)
// printf("%d ", f1[i][j]);
// puts("");
// }
for (int i = 1; i <= n; i++)
for (int j = m; j >= 1; j--)
if (A[i][j] == 0) continue;
else f2[i][j] = f2[i][j + 1] + 1;
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++)
// printf("%d ", f2[i][j]);
// puts("");
// }
for (int i = n; i >= 1; i--)
for (int j = 1; j <= m; j++)
if (A[i][j] == 0) continue;
else f3[i][j] = f3[i + 1][j] + 1;
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++)
// printf("%d ", f3[i][j]);
// puts("");
// }
for (int w = a; w <= m; w++)
for (int h = b; h <= n; h++)
g[w][h] = g[w - 1][h] + g[w][h - 1] - g[w - 1][h - 1] + g1(w, h);
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (A[i][j] == 0) continue;
else ans += g[(min(f1[i][j], f2[i][j])) * 2 - 1][f3[i][j]];
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++)
// if (A[i][j] == 0) printf("0 ");
// else printf("%d ", g[(min(f1[i][j], f2[i][j])) * 2 - 1][f3[i][j]]);
// puts("");
// }
// for (int i = 1; i <= m; i++) {
// for (int j = 1; j <= n; j++)
// printf("%d ", g[i][j]);
// puts("");
// }
printf("%d\n", ans);
return 0;
}
我已经分别将 f1,f2,f3,g 以及每次更新给答案的量都输出了,但还是调不出来,求助。
样例 1 比答案多 1,样例 2,3 比答案多 2。