条破防了,求从原来代码上改,用的前缀和优化,到了 O(n4),但只有 75 分……
代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int a[15][15];
int sum[15][15];
int n,m;
int ans=-1;
bool check(int x,int y,int x_,int y_){
int cnt=sum[x_][y_]-sum[x-1][y_]-sum[x_][y-1]+sum[x-1][y-1];
if(cnt==(x_-x+1)*(y_-y+1)/2) return 1;
else return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char x;
cin>>x;
a[i][j]=x-'0';
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
}
}
for(int x=1;x<=n;x++){
for(int y=1;y<=m;y++){
for(int x_=x;x_<=n;x_++){
for(int y_=y;y_<=m;y_++){
if(check(x,y,x_,y_)) ans=max(ans,(x_-x+1)*(y_-y+1));
}
}
}
}
if(ans==-1) cout<<0<<endl;
else cout<<ans<<endl;
return 0;
}