Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Fast solution in Speedy category for Spaceship Landing Strip by vikulin
def checkio(land_map):
height, width, maxrect = len(land_map), len(land_map[0]), 0
sq = {}
# very fast matrix creation
up = [x[:] for x in [[0] * width] * height]
left = [x[:] for x in [[0] * width] * height]
# fill in up and left matricies and sq for each lower-right corner
for r in range(height):
for c in range(width):
if land_map[r][c] in 'GS':
up[r][c] = 1 + (up[r-1][c] if r-1 >= 0 else 0)
left[r][c] = 1 + (left[r][c-1] if c-1 >= 0 else 0)
sq[(r,c)] = up[r][c] * left[r][c]
# find the largest rect starting with the most promising lower-right corner
for (r, c), square in sorted(sq.items(), key=lambda x: x[1], reverse=True):
if maxrect >= square:
return maxrect
rect, h = 0, height
for w in range(left[r][c]):
h = min(h, up[r][c-w])
rect = max(rect, h * (w + 1))
maxrect = max(maxrect, rect)
return maxrect
Oct. 23, 2015
Comments:
