详细请查看注释
参考代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010;
int n, m, Q, l[N], r[N], s[N][N], q[N];
int U[N], D[N], L[N], R[N];
char g[N][N];
/*
本题关键是要看出是一个单调栈模型!---> 类似求最大矩形面积一样!
单调栈问题:求解左边或右边第一个比它小的数!---> 正好用来求最大矩形!
思路:将整个矩阵按照行或列为底部的 最大矩形面积 一样,处理为一个单调栈问题即可!
本题不同之处:每次询问都会将该位置置为0,因此我们的最大矩形一定不包含该点,因此他一定在该点的上下左右
四个方向的其中一个两个或三个方向!
因此:直接枚举该四个方向的最大矩形即可!最后再取一次最大值即可!
关于求解每一层的每一列的矩形高度:可以直接判断该位置的状态即可:(以上为例)
0:0
1:该位置上侧1的个数 + 当前位置1的个数1
关于求解每一层的最大矩形:max(上一层最大矩形面积,该层最大面积)
*/
int calc(int h[], int n){
int tt = 0; q[0] = 0, h[0] = -1;
for(int i = 1; i <= n; i ++){
while(h[q[tt]] >= h[i]) tt --;
l[i] = q[tt], q[++ tt] = i;
}
tt = 0; q[0] = n + 1, h[n + 1] = -1;
for(int i = n; i >= 1; i --){
while(h[q[tt]] >= h[i]) tt --;
r[i] = q[tt], q[++ tt] = i;
}
int res = 0;
for(int i = 1; i <= n; i ++) res = max(res, h[i] * (r[i] - l[i] - 1));
return res;
}
void init(){
// 上
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++)
if(g[i][j] == '1') s[i][j] = s[i - 1][j] + 1;
else s[i][j] = 0;
U[i] = max(U[i - 1], calc(s[i], m));
}
// 下
memset(s, 0, sizeof s);
for(int i = n; i >= 1; i --){
for(int j = 1; j <= m; j ++)
if(g[i][j] == '1') s[i][j] = s[i + 1][j] + 1;
else s[i][j] = 0;
D[i] = max(D[i + 1], calc(s[i], m));
}
// 左
memset(s, 0, sizeof s);
for(int i = 1; i <= m; i ++){
for(int j = 1; j <= n; j ++)
if(g[j][i] == '1') s[i][j] = s[i - 1][j] + 1;
else s[i][j] = 0;
L[i] = max(L[i - 1], calc(s[i], n));
}
// 右
memset(s, 0, sizeof s);
for(int i = m; i >= 1; i --){
for(int j = 1; j <= n; j ++)
if(g[j][i] == '1') s[i][j] = s[i + 1][j] + 1;
else s[i][j] = 0;
R[i] = max(R[i + 1], calc(s[i], n));
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> g[i] + 1;
init();
cin >> Q;
while(Q --){
int x, y; cin >> x >> y;
x ++, y ++;
cout << max(max(U[x - 1], D[x + 1]), max(L[y - 1], R[y + 1])) << endl;
}
return 0;
}