C++ 代码
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 2010;
char s[N][N];
int Q, x, y, n, m, q[N], tt, a[N], u[N], d[N], l[N], r[N], L[N], R[N];
int calc(int a[], int n) {
a[0] = a[n + 1] = -1;
q[tt = 0] = 0;
for (int i = 1; i <= n; i++) {
while (a[q[tt]] >= a[i])tt--;
L[i] = q[tt];
q[++tt] = i;
}
q[tt = 0] = n + 1;
for (int i = n; i >= 1; i--) {
while (a[q[tt]] >= a[i])tt--;
R[i] = q[tt];
q[++tt] = i;
}
int res = 0;
for (int i = 1; i <= n; i++)
res = max(res, (R[i] - L[i] - 1) * a[i]);
return res;
}
void init() {
memset(a, 0, sizeof a);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
if (s[i][j] == '1')a[j]++;
else a[j] = 0;
u[i] = max(u[i - 1], calc(a, m));
}
memset(a, 0, sizeof a);
for (int i = n; i; i--) {
for (int j = 1; j <= m; j++)
if (s[i][j] == '1')a[j]++;
else a[j] = 0;
d[i] = max(d[i + 1], calc(a, m));
}
memset(a, 0, sizeof a);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++)
if (s[j][i] == '1')a[j]++;
else a[j] = 0;
l[i] = max(l[i - 1], calc(a, n));
}
memset(a, 0, sizeof a);
for (int i = m; i; i--) {
for (int j = 1; j <= n; j++)
if (s[j][i] == '1')a[j]++;
else a[j] = 0;
r[i] = max(r[i + 1], calc(a, n));
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%s", s[i] + 1);
init();
scanf("%d", &Q);
while (Q--) {
scanf("%d%d", &x, &y);
cout << max(u[x], max(d[x + 2], max(l[y], r[y + 2]))) << endl;
}
return 0;
}