Codeforces Round #22 (Div 2 only) B. Bargaining Table

問題概要

nxmのグリッドで表される部屋があり、既に家具の置かれているマスは1,何も置かれていないマスは0で表された部屋の状態が与えられる。
既に置かれている家具に重ならないよう置ける長方形の家具のうち、最大の周長のものの周長を求めよ。

n,m≤25を満たす。

解法

n,mは小さいので全通り試すO((n*m)^3)の解法で間に合う。

ソースコード

char ocp[30][30];

bool check(int y,int Y,int x,int X)
{
        for(int i=y;i<Y;i++)for(int j=x;j<X;j++)
        if(ocp[i][j]=='1')return 0;
        return 1;
}

void run()
{
        int h,w; cin>>h>>w;
        rep(i,h)cin>>ocp[i];
        
        int ans=0;
        rep(i,h)rep(j,w)if(ocp[i][j]=='0')
        {
                for(int ii=i+1;ii<=h;ii++)
                {
                        bool ok=0;
                        for(int jj=j+1;jj<=w;jj++)
                        {
                                if(check(i,ii,j,jj))
                                ok=1,ans=max(ans,(ii-i+jj-j)*2);
                                else break;
                        }
                        if(!ok)break;
                }
        }
        cout<<ans<<endl;
}