SPOJ: 277. City Game

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