Pagini recente » Cod sursa (job #1038374) | Cod sursa (job #3129010) | Cod sursa (job #631376) | Cod sursa (job #2182205) | Cod sursa (job #590587)
Cod sursa(job #590587)
#include<stdio.h>
#define maxN 205
FILE*f=fopen("bmatrix.in","r");
FILE*g=fopen("bmatrix.out","w");
int n,m,i,j,D[maxN][maxN],Sol;
int vf,St[maxN],arie,Drept[4][maxN];
char A[maxN][maxN],Cpy[maxN][maxN];
void findmax ( char A[maxN][maxN] , int M[maxN] ){
int i,j,p;
for ( i = 1 ; i <= n ; ++i ){
for ( j = 1 ; j <= m ; ++j ){
if ( A[i][j] ){
D[i][j] = 0;
}
else
D[i][j] = D[i-1][j] + 1;
}
}
for ( i = 1 ; i <= n ; ++i ){
M[i] = M[i-1];
for ( j = 1 , vf = 0 ; j <= m ; ++j ){
p = St[vf];
while ( vf && D[i][j] < D[i][ St[vf] ] ){
arie = D[i][ St[vf] ] * ( p - St[vf-1] );
M[i] = M[i] > arie ? M[i] : arie;
--vf;
}
St[++vf] = j;
}
for ( p = St[vf] ; vf ; --vf ){
arie = D[i][ St[vf] ] * ( p - St[vf-1] );
M[i] = M[i] > arie ? M[i] : arie;
}
}
}
void rotate_right( char A[maxN][maxN] ){
int i,j;
for ( i = 1 ; i <= n ; ++i ){
for ( j = 1 ; j <= m ; ++j ){
Cpy[i][j] = A[i][j];
A[i][j] = 0;
}
}
for ( i = 1 ; i <= n ; ++i ){
for ( j = 1 ; j <= m ; ++j ){
A[j][n - i + 1] = Cpy[i][j];
}
}
}
inline void swap( int &a, int &b ){
int aux = a;
a = b;
b = aux;
}
inline void solve () {
int i,j;
for ( i = 1; i < n ; ++i ){
if ( Drept[0][i] + Drept[2][n-i] > Sol ){
Sol = Drept[0][i] + Drept[2][n-i];
}
}
for ( j = 1 ; j < m ; ++j ){
if ( Drept[1][j] + Drept[3][m-j] > Sol ){
Sol = Drept[1][j] + Drept[3][m-j];
}
}
fprintf(g,"%d\n",Sol);
}
int main () {
fscanf(f,"%d %d",&n,&m);
for ( i = 1 ; i <= n ; ++i ){
fscanf(f,"%s",A[i]+1);
for ( j = 1 ; j <= m ; ++j )
A[i][j] -= '0';
}
for ( i = 0 ; i < 4 ; ++i ){
findmax(A,Drept[i]);
rotate_right(A);
swap(n,m);
}
solve();
fclose(f);
fclose(g);
return 0;
}