SRM455 Div1 Easy

ある長方形の領域中の解は、周囲の4辺の１つを切り落としたモノの最大値 or 4辺全てを切り落としたモノ+1

const int H = 50;
const int W = 50;
int t[H][W][H][W];
bool rect[H][W][H][W];

int rec(int a, int b, int c, int d)
{
  if( a > c || b > d )return 0;
  if( t[a][b][c][d] != -1 )return t[a][b][c][d];
  
  int mx = 0;
  
  mx = max( mx, rec(a+1, b, c, d) );
  mx = max( mx, rec(a, b+1, c, d) );
  mx = max( mx, rec(a, b, c-1, d) );
  mx = max( mx, rec(a, b, c, d-1) );

  if( rect[a][b][c][d] ){
    mx = max( mx, rec(a+1, b+1, c-1, d-1) + 1 );
  }
  
  return t[a][b][c][d] = mx;
}

class DonutsOnTheGridEasy {
public:
  int calc(vector <string> g) {
    
    const int h = g.size();
    const int w = g[0].size();
    
    fill( &t[0][0][0][0], &t[H-1][W-1][H-1][W], -1 );
    fill( &rect[0][0][0][0], &rect[H-1][W-1][H-1][W], false );

    for(int i=0; i<h; ++i){
      for(int j=0; j<w; ++j){
        for(int k=i+2; k<h; ++k){
          for(int l=j+2; l<w; ++l){
            bool flg = true;
            for(int m=i; m<=k && flg; ++m){
              flg = g[m][j] == '0' && g[m][l] == '0';
            }
            if( !flg )continue;
            for(int m=j; m<=l && flg; ++m){
              flg = g[i][m] == '0' && g[k][m] == '0';
            }
            if( !flg )continue;
            //cout << i << ' ' << j << " : " << k << ' ' << l << endl; 
            rect[i][j][k][l] = true;
          }
        }
      }
    }

    return rec(0, 0, h-1, w-1);
  }
};