You are viewing a single comment's thread. Return to all 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
Seems like cookies are disabled on this browser, please enable them to open this website
Ema's Supercomputer
You are viewing a single comment's thread. Return to all comments →
python solution (it took me way more time than expected):