Pagini recente » Cod sursa (job #2243462) | Cod sursa (job #717054) | Cod sursa (job #3152683) | Cod sursa (job #350550) | Cod sursa (job #2228782)
#include <bits/stdc++.h>
#define N 205
using namespace std;
ifstream fin("bmatrix.in") ;
ofstream fout("bmatrix.out") ;
int mat[N][N] , dp[N][N][5] , M1[N][N][5] ;
int n , m ;
int euclid(int a, int b)
{
int c;
while (b)
{
c = a % b;
a = b;
b = c;
}
return a;
}
int vizitez( int ct , int x , int y , int mx )
{
int i , j , maxima = -1, ctx;
if ( mat[x-1][y] == 0 )
ctx = euclid(mx,dp[x-1][y][2]) ;
else
ctx = euclid(mx,dp[x][y-1][2]) ;
int cty = mx/ctx ;
for ( i = x ; i > x - cty ; i-- )
for ( j = y ; j > y - ctx ; j-- )
M1[i][j][ct] =1 ;
/*for ( i = 1 ; i <= n ; i++ )
{
for ( j = 1 ; j <= m ; j++ )
cout << M1[i][j][ct] << " " ;
cout << endl ;
}
cout << endl << endl ;
*/
for ( i = 1 ; i <= n ; i++ )
{
for ( j = 1 ; j <= m ; j++ )
{
if ( M1[i][j][ct] == 0 )
dp[i][j][ct] = dp[i-1][j][ct]+dp[i][j-1][ct]-dp[i-1][j-1][ct]+1 ;
maxima = max(maxima,dp[i][j][ct]) ;
}
}
return maxima+mx;
}
int main()
{
int i , j , maxim , maxim2 , m1x , m2x , m1y , m2y ;
char ch;
fin >> n >> m ;
for ( i = 1 ; i <= n ; i++ )
{
for ( j = 1 ; j <= m ; j++ )
{
fin >> ch ;
mat[i][j] = ch - '0' ;
M1[i][j][0] = mat[i][j] ;
M1[i][j][1] = mat[i][j] ;
}
}
maxim = -1;
m1x = 1 ;
m1y = 1 ;
for ( i = 1 ; i <= n ; i++ )
{
for ( j = 1 ; j <= m ; j++ )
{
if ( mat[i][j] == 0 )
dp[i][j][2] = dp[i-1][j][2]+dp[i][j-1][2]-dp[i-1][j-1][2]+1 ;
if ( maxim < dp[i][j][2] )
{
maxim2 = maxim ;
m2x = m1x ;
m2y = m1y ;
maxim = dp[i][j][2] ;
m1x = i ;
m1y = j ;
}
// cout << dp[i][j][2] << " " ;
}
// cout << endl ;
}
//cout << maxim << " " << maxim2 << " " << m1x << " " << m1y << endl ;
//cout << endl << endl;
//cout << vizitez(0,m1x,m1y,maxim) << " " ;
//cout << vizitez(1,m2x,m2y,maxim2) ;
fout << max(vizitez(0,m1x,m1y,maxim),vizitez(1,m2x,m2y,maxim2)) ;
}