给你一个 01 矩阵,求满足第一行、最后一行、第一列、最后一列均无 0 的最大子矩阵面积。\(n,m<=200\)。
不难想到对于每个点,预处理出,向其上下左右最大限度扩展。这种方法类似于单调栈的预处理。
预处理后,以每个点为矩阵左上角,向右下枚举矩阵右上角。此时我们已经确定了这个矩阵的第一行、第一列满足条件,只需判断最后一行和最后一列是否满足条件即可。
加上一些优化。我们认为这样的复杂度大概能被允许。
#include<bits/stdc++.h>
using namespace std;
const int N=202;
int n,m;
int a[N][N];
int s[N][N][5];
//0上1下2左3右
int ans;
int main(){
scanf("%d%d",&n,&m);
memset(a,-1,sizeof a);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char c;
cin>>c;
if(c=='X') a[i][j]=0;
else a[i][j]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
for(int q=i;q>=1;q--){
if(!a[q][j]) break;
s[i][j][0]=q;
}
for(int q=i;q<=n;q++){
if(!a[q][j]) break;
s[i][j][1]=q;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
for(int q=j;q>=1;q--){
if(!a[i][q]) break;
s[i][j][2]=q;
}
for(int q=j;q<=m;q++){
if(!a[i][q]) break;
s[i][j][3]=q;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(!a[i][j]) continue;
if((s[i][j][1]-s[i][j][0]+1)*(s[i][j][3]-s[i][j][2]+1)<=ans) continue;
for(int x=i;x<=s[i][j][1];x++){
for(int y=j;y<=s[i][j][3];y++){
if(s[x][y][0]<=i&&s[x][y][2]<=j)
ans=max(ans,(x-i+1)*(y-j+1));
}
}
if(ans==n*m){
printf("%d",ans);
return 0;
}
}
printf("%d",ans);
return 0;
}