The strategic task of his game is to win as much rent money from these free spaces. To win rent money you must erect buildings, that can only be rectangular, as long and wide as you can. Bob is trying to find a way to build the biggest possible building in each area.
Problem: Sphere Online Judge (SPOJ) – Problem CTGAME
Solution: The basic idea behind my algorithm is to expand rectangles continuously. It looks for a free space, marks it as a rectangle with the size 1×1 and expands in each direction alternately.
def checkRight(f, i, j):
if j >= int(w) - 1 or i > int(h) - 1:
return False
else:
if f[i][j+1] == 'F':
return True
else:
return False
def checkBottom(f, i, j):
if i >= int(h) - 1 or j > int(w) - 1:
return False
else:
if f[i+1][j] == 'F':
return True
else:
return False
def checkSelf(f, i, j):
if field[i][j] == 'F':
return True
else:
return False
def checkExpandWidth(f, i, j, height, width):
for y in xrange(i, height + i):
if checkRight(field, y, j + width - 1) == False:
return False
return True
def checkExpandHeight(f, i, j, height, width):
for x in xrange(j, width + j):
if checkBottom(field, i + height - 1, x) == False:
return False
return True
k = int(raw_input())
for areas in xrange(0, k):
line = raw_input()
h, w = line.split()
field = []
for li in xrange(0, int(h)):
line = raw_input()
field.append(line.split())
# blank line
try:
t = raw_input()
except:
break
maxSquare = 0
for i in xrange(0, int(h)):
for j in xrange(0, int(w)):
if checkSelf(field, i, j) == False:
continue
else:
height = 1
width = 1
eWidth = True
eHeight = True
# expand width first
while eWidth == True or eHeight == True:
if eWidth == True and checkExpandWidth(field, i, j, height, width) == True:
width += 1
else:
eWidth = False
if eHeight == True and checkExpandHeight(field, i, j, height, width) == True:
height += 1
else:
eHeight = False
# found bigger square
if height * width > maxSquare:
maxSquare = height * width
# reset vars
height = 1
width = 1
eWidth = True
eHeight = True
# expand height first
while eWidth == True or eHeight == True:
if eHeight == True and checkExpandHeight(field, i, j, height, width) == True:
height += 1
else:
eHeight = False
if eWidth == True and checkExpandWidth(field, i, j, height, width) == True:
width += 1
else:
eWidth = False
# found bigger square
if height * width > maxSquare:
maxSquare = height * width
print maxSquare * 3