• + 0 comments

    python solution (it took me way more time than expected):

    class Plus:
        def __init__(self, i, j, k):
            self.i = i
            self.j = j
            self.k = k
        
        def is_disjoint(self, another):
            if self.i == another.i:
                if self.j > another.j and self.j - self.k <= another.j + another.k:
                    return False
                if self.j < another.j and self.j + self.k >= another.j - another.k:
                    return False
            if self.j == another.j:
                if self.i > another.i and self.i - self.k <= another.i + another.k:
                    return False
                if self.i < another.i and self.i + self.k >= another.i - another.k:
                    return False
            
            if another.i - another.k <= self.i <= another.i + another.k:
                if self.j - self.k <= another.j <= self.j + self.k:
                    return False
            if another.j - another.k <= self.j <= another.j + another.k:
                if self.i - self.k <= another.i <= self.i + self.k:
                    return False
            return True
            
    def get_pluses(grid, i, j, k_range):
        n = len(grid)
        m = len(grid[0])
        
        pluses = [Plus(i, j, 0)]
        for k in range(1, k_range):
            if i - k < 0 or i + k >= n:
                return pluses
            if j - k < 0 or j + k >= m:
                return pluses
                    
            positions = [(i - k, j), (i, j + k), (i + k, j), (i, j - k)]
            for pos in positions:
                if grid[pos[0]][pos[1]] != 'G':
                    return pluses
            pluses.append(Plus(i, j, k))
        return pluses
    
    def twoPluses(grid):
        n = len(grid)
        m = len(grid[0])
        minimum_size = min(n, m)
        pluses = []
        
        for i in range(n):
            for j in range(m):
                if grid[i][j] != 'G':
                    continue
                pluses += get_pluses(grid, i, j, (minimum_size+1)//2)
        
        maximum_area = 0
        for index_plus0 in range(len(pluses) - 1):
            for index_plus1 in range(index_plus0 + 1, len(pluses)):
                if pluses[index_plus0].is_disjoint(pluses[index_plus1]):
                    area0 = pluses[index_plus0].k * 4 + 1
                    area1 = pluses[index_plus1].k * 4 + 1
                    current_area = area0 * area1
                    if current_area > maximum_area:
                        maximum_area = current_area
        return maximum_area