题目链接:
codeforces 22B
题目大意:
给出一个矩阵,求周长最大的矩形的周长
题目分析:
求出每个点为底的最大的高度(0),然后枚举右下角,再枚举矩形的高度,,然后算取长度,进而算取周长即可。
AC代码:;int n,m;char a[MAX][MAX];int h[MAX][MAX];int l[MAX][MAX];int r[MAX][MAX];int main ( ){while ( ~scanf ( “%d%d” , &n , &m ) ){for ( int i = 0 ; i < n ; i++ )scanf ( “%s” , a[i] );for ( int i = 0 ; i < n ; i++ )for ( int j = 0 ; j < m ; j++ ){if ( a[i][j] == ‘1’ ){h[i][j] = 0;continue;}if ( i == 0 || a[i-1][j] == ‘1’ )h[i][j] = 1;else h[i][j] = h[i-1][j] + 1;}int ans = 0;for ( int i = 0 ; i < n ; i++ )for ( int j = 0 ; j < m ; j++ )for ( int k = 1 ; k <= h[i][j] ; k++ ){int l = j;while ( l >= 0 && h[i][l] >= k )l–;ans = max ( ans , (j-l)+k );}printf ( “%d\n” , ans*2 );}}
从起点,到尽头,也许快乐,或有时孤独,