How to 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] &amp;&amp; dp[x1][y1][x2][y2-1] &amp;&amp; (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.
Your approach is basically correct. However, be sure to pay attention to a few boundary cases besides the general cases for x2>x1 and y2>y1.


Initialize the tables on a single square, i.e., dp[x][y][x][y] = (board[x][y] == 0);
Compute the case when the table can be on a single column, dp[x1][y][x2][y] = dp[x1][y][x2-1][y] &amp;&amp; (board[x2][y] == 0), where x2>x1.
Compute the case when the table can be on a single row, dp[x][y1][x][y2] = dp[x][y1][x][y2-1] &amp;&amp; (board[x][y2] == 0), where y2>y1.


For brevity, those boundary cases are not mentioned explicitly in the editorial. Once those cases are included, the algorithm will be fully correct.