Represent the grid by a 0-1 matrix where a 1 corresponds to an obstacle.
If the grid is m x n and (a,b) are the 0-based row and column indices of the starting cell, then width = n-b represents the maximum possible width of a rectangle starting at that cell, irrespective of any obstacles. This is the current width. Now, start scanning down the column from that cell until either the bottom edge or an obstacle is encountered. For each cell in that column, start scanning right until either an obstacle or the current width is reached. If an obstacle is encountered first, decrease the current width. Append the current width to a list of widths (whether or not the current width had been decreased).
At this stage, you have a list of widths, with one width for every potential height. Just scan over this list, multiplying each width by the corresponding height (which would be 1 + the 0-based list index). Return the pair (height,width) which maximized the product height*width.
A Python implementation:
def find_max_rect(grid,a,b):
if grid[a][b] == 1: return (0,0)
m = len(grid) #number of rows
n = len(grid[0]) #number of columns
width = n-b #maximum possible width given starting column
widths = []
i = a
while i < m and grid[i][b] == 0:
#scan right from (i,b+1) until a 1 or current width is hit
for j in range(b+1,b+width):
if grid[i][j] == 1:
#an obstacle forces width to contract
width = j-b #number of steps before obstacle
break #out of inner loop
widths.append(width)
i += 1
max_area = 0
max_at = -1
for i,width in enumerate(widths):
if (i+1)*width > max_area:
max_area = (i+1)*width
max_at = i
return (max_at + 1,widths[max_at])
Tested like:
test_grid = [[1,0,1,1,0],
[0,1,0,0,0],
[0,1,0,0,0],
[0,1,0,0,0],
[0,0,0,1,0],
[0,0,0,1,0],
[0,0,0,0,1],
[0,0,0,0,0],
[1,0,0,0,0],
[0,0,0,0,1],
[0,1,0,0,0]]
print(find_max_rect(test_grid,6,2)) #prints (5,2)
On Edit: I realized that there is little reason to store the candidate widths only to iterate over them just once. Instead, you can keep track of the best area on the fly. The following code is functionally equivalent but more efficient:
def find_max_rect(grid,a,b):
if grid[a][b] == 1: return (0,0)
m = len(grid) #number of rows
n = len(grid[0]) #number of columns
current_height = 0
current_width = n - b #maximum possible width given starting column
max_area = 0
best_height, best_width = current_height, current_width
i = a
while i < m and grid[i][b] == 0:
current_height += 1
#scan right from (i,b + 1) until a 1 or current width is hit
for j in range(b + 1,b + current_width):
if grid[i][j] == 1:
#an obstacle forces width to contract
current_width = j - b #number of steps before obstacle
break
#decide if the best should be adjusted
current_area = current_height * current_width
if current_area > max_area:
best_area, best_height, best_width = current_area, current_height, current_width
i+=1
return best_height, best_width
.