CodeForces 22B Bargaining Table 01矩阵求最大矩形面积
///不想再说什么了，hdu和poj的数据真心弱。///这题和hdu1505一样的思路。#include<iostream>#include<cstdlib>#include<stdio.h>#include<memory.h>using namespace std;const int N=30;char str[N][N];//int mat[N][N];int h[N][N];int l[N][N];int r[N][N];int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF) { memset(h,0,sizeof(h)); for(int i=0;i<n;i++) scanf("%s",str[i]); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { if(str[i][j]=='0') h[i+1][j+1]=h[i][j+1]+1; else h[i+1][j+1]=0; } for(int i=1;i<=n;i++) { l[i][1]=1; r[i][m]=m; } for(int i=1;i<=n;i++) { for(int j=2;j<=m;j++) { int t=j; while(t>1&&h[i][j]<=h[i][t-1]&&h[i][j]!=0)///h[i][j]!=0很重要 t=t-1; l[i][j]=t; } } for(int i=1;i<=n;i++) for(int j=m-1;j>=1;j--) { int t=j; while(t<m&&h[i][j]<=h[i][t+1]&&h[i][j]!=0) t=t+1; r[i][j]=t; } int maxn=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int s=(r[i][j]-l[i][j]+1+h[i][j])*2; // cout<<l[i][j]<<" "<<r[i][j]<<" "<<"&"<<" "<<i<<" "<<j<<" "<<s<<" *"<<endl; if(s>maxn) maxn=s; } cout<<maxn<<endl; }}
