Find Maximum perimeter of rectangle in a grid with obstacles (Dynamic Programming)

Can someone tell me what am I doing wrong?

Problem: https://codeforces.com/contest/22/problem/B

Editorial: https://codeforces.com/blog/entry/507 ( I followed the DP solution O((n*m)^2) )

Eg:

00001
00000
10100     //ans is 12

####1
####0
10100

My approach: rectangle with coordinates (x1, y1, x2, y2) is correct if and only if rectangles (x1, y1, x2-1, y2) and (x1, y1, x2, y2-1) are correct, and board[x2][y2] = ‘0’.

ie: dp[x1][y1][x2][y2]=(dp[x1][y1][x2-1][y2] && dp[x1][y1][x2][y2-1] && (board[x2][y2]==0))

If it is correct then find it’s perimeter (perimeter = 2*(x2-x1+y2-y1+2)) ie ans=max(ans,perimeter)

And dp[x1][y1][x2][y2]=1 for all i,j when board[x2][y2]==0. Because from point p1 to point p1, ie the same point always have a perimeter is the base case.

signed main(){
    int r,c;cin>>r>>c;
    vector<vi> v(r,vi(c));
    bool dp[25][25][25][25]={false};//i,j to p,q
    for(int i=0;i<r;i++){
        string s;cin>>s;
        for(int j=0;j<c;j++){
            v[i][j]=(s[j]-'0');
            if(v[i][j]==0)dp[i][j][i][j]=true;
        }
    }
    int ans=-1;
    for(int i=0;i<r;i++){//x1
        for(int j=0;j<c;j++){//y1
            for(int p=i;p<r;p++){//x2
                for(int q=j;q<c;q++){//y2
                    //i,j to p,q , 0,0 0,2, afrom 1 to p, b from 1 to q
                    if(!(i==p && j==q)){
                        if(p-1>=0 && q-1>=0)
                            dp[i][j][p][q]=(dp[i][j][p-1][q] && dp[i][j][p][q-1] && (v[p][q]==0));
                        //cout<<dp[i][j][p][q]<<i<<j<<p<<q<<"\n";
                        if(dp[i][j][p][q]==true){
                            ans=max(ans,2*(p-i+q-j+2));
                            //cout<<"^";
                        }
                    }
                }
            }
        }
    }
    cout<<ans;
}

Your logic is almost correct but you forgot some edge-cases.

You are not checking the cases when there is only a row.
Take for example : 001

Fix lines starting from :

1 Like

Yes, Fixed it already. :slight_smile: