• + 0 comments
    #!/bin/python3
    
    import math
    import os
    import random
    import re
    import sys
    
    #
    # Complete the 'twoPluses' function below.
    #
    # The function is expected to return an INTEGER.
    # The function accepts STRING_ARRAY grid as parameter.
    #
    
    def twoPluses(grid):
        # Write your code here
        n, m = len(grid), len(grid[0])
        up = [[0]*m for _ in range(n)]
        down = [[0]*m for _ in range(n)]
        left = [[0]*m for _ in range(n)]
        right = [[0]*m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 'G':
                    up[i][j] = 1 + (up[i-1][j] if i > 0 else 0)
                    left[i][j] = 1 + (left[i][j-1] if j > 0 else 0)
        for i in reversed(range(n)):
            for j in reversed(range(m)):
                if grid[i][j] == 'G':
                    down[i][j] = 1 + (down[i+1][j] if i < n-1 else 0)
                    right[i][j] = 1 + (right[i][j+1] if j < m-1 else 0)
    
        pluses = []
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 'G':
                    arm_len = min(up[i][j], down[i][j], left[i][j], right[i][j]) - 1
                    for length in range(arm_len + 1):
                        pluses.append((i, j, length, 4*length + 1))  # (row, col, arm, area)    
        def cells_of_plus(r, c, arm):
            cells = {(r, c)}
            for k in range(1, arm+1):
                cells.add((r+k, c))
                cells.add((r-k, c))
                cells.add((r, c+k))
                cells.add((r, c-k))
            return cells
    
        max_product = 0
        for i in range(len(pluses)):
            r1, c1, arm1, area1 = pluses[i]
            cells1 = cells_of_plus(r1, c1, arm1)
            for j in range(i+1, len(pluses)):
                r2, c2, arm2, area2 = pluses[j]
                cells2 = cells_of_plus(r2, c2, arm2)
                if cells1.isdisjoint(cells2):
                    product = area1 * area2
                    if product > max_product:
                        max_product = product
        return max_product
    
    
    if __name__ == '__main__':
        fptr = open(os.environ['OUTPUT_PATH'], 'w')
    
        first_multiple_input = input().rstrip().split()
    
        n = int(first_multiple_input[0])
    
        m = int(first_multiple_input[1])
    
        grid = []
    
        for _ in range(n):
            grid_item = input()
            grid.append(grid_item)
    
        result = twoPluses(grid)
    
        fptr.write(str(result) + '\n')
    
        fptr.close()