0w1

HR Mr K marsh ( DP )

https://www.hackerrank.com/challenges/mr-k-marsh
First, precompute the leftmost and uppermost cell each cell can reach to. Then, enumerate 2 rows each time, push each column where it the vertical fence could be built into a vector. Then, use crawling technique to find the maximum range in horizontal dimension. O( N ^ 3 ).

#include <bits/stdc++.h>
using namespace std;
const int MAXM = 500 + 5;
const int MAXN = 500 + 5;

int M, N;
char G[ MAXM ][ MAXN ];

int tol[ MAXM ][ MAXN ]; // maximum length reachable towards left
int tou[ MAXM ][ MAXN ]; // including the cell itself

void solve(){
    for( int i = 1; i <= M; ++i )
        for( int j = 1; j <= N; ++j ){
            if( G[ i ][ j ] == 'x' )
                tol[ i ][ j ] =
                tou[ i ][ j ] = 0;
            else
                tol[ i ][ j ] = tol[ i ][ j - 1 ] + 1,
                tou[ i ][ j ] = tou[ i - 1 ][ j ] + 1;
        }
    int ans = -1;
    for( int r1 = 1; r1 <= M; ++r1 )
        for( int r2 = r1 + 1; r2 <= M; ++r2 ){
            vector< int > col;
            for( int c = 1; c <= N; ++c )
                if( tou[ r2 ][ c ] >= r2 - r1 + 1 ) // this column has no problem being between r1 and r2
                    col.push_back( c );
            int lidx = 0, ridx;
            for( ridx = 0; ridx < col.size(); ++ridx ){
                int threshold = col[ ridx ] - min( tol[ r1 ][ col[ ridx ]  ], tol[ r2 ][ col[ ridx ] ] ) + 1; // crawl, get the minimum threshold for lidx
                while( col[ lidx ] < threshold ) ++lidx;
                if( col[ ridx ] > col[ lidx ] ) // update answer
                    ans = max( ans, 2 * ( r2 - r1 - 1 + col[ ridx ] - col[ lidx ] - 1 ) + 4 );
            }
        }
    if( ans == -1 ) puts( "impossible" );
    else printf( "%d\n", ans );
}

int main(){
    scanf( "%d%d", &M, &N );
    for( int i = 1; i <= M; ++i )
        scanf( "%s", G[ i ] + 1 );
    solve();
    return 0;
}