#!/usr/bin/python3 class Node: """Jeden vrchol kvadrantového stromu (vnitřní nebo list).""" def __init__(self, color, children): self.color = color self.children = children self.S = {} # Pomocné pointery S_s pro hledání sousedů, viz řešení self.neighs = set() # Finální seznam sousedů v grafu sousednosti self.visited = False # Byl již navštíven při hledání komponent? # Souřadnice jednotlivých kvadrantů v pořadí, v jakém jsou zapsány na vstupu QUADRANTS = [(0,0), (1,0), (0,1), (1,1)] def parse(): """Převeď (pod)čtverec začínající v kvadrantovém kódu v proměnné `code` na pozici `idx` na kvadrantový strom. Na konci posuň ukazatel `idx` za konec zpracované části kódu.""" global code, idx if code[idx] in '01': node = Node(int(code[idx]), {}) idx += 1 elif code[idx] == '(': idx += 1 children = {} for quad in QUADRANTS: children[quad] = parse() if code[idx] != ')': raise ValueError("Neplatný kód") idx += 1 node = Node(None, children) return node def get_depth(node): """Urči hloubku stromu.""" if node.children: return max( get_depth(child) for child in node.children.values() ) + 1 else: return 0 def add_areas(node, area): """Přidej k vrcholům informaci o ploše.""" node.area = area for child in node.children.values(): add_areas(child, area//4) # Kvadranty mají čtvrtinovou plochu def add(u, v): """Vektorové sčítání""" return (u[0]+v[0], u[1]+v[1]) # pro odvážlivce: return tuple(map(sum, zip(u, v))) DIRS=[(-1,0), (1,0), (0,-1), (0,1)] def find_neighbours(node, parent=None, pos=None): """Najdi graf sousednosti kvadrantového stromu (rekurzivní funkce).""" if parent is not None: for dir in DIRS: neighpos = add(pos, dir) if neighpos in QUADRANTS: # Sousední kvadrant je náš stromový sourozenec neigh = parent.children[neighpos] else: # Přešli jsme přes hranici aktuálního čtverce (pos je např. (0,2)). # V takovém případě není soused stromovým sourozencem a musíme hledat # jinde. parent_neigh = parent.S.get(dir, None) if parent_neigh is None: neigh = None elif parent_neigh.children: # Soused rodiče je podrozdělen, musí se tedy nacházet ve stejné # hloubce (zdůvodněno v řešení). Musíme vybrat toho z jeho # synů, který přiléhá k aktuálnímu vrcholu. Pokud nám tenhle # kód nevěříte, nakreslete si to. adj_pos = list(pos) # Pokud se posouváme ve vodorovném směru, např. pravý soused # pravého kvadrantu je levým kvadrantem nějakého jiného vrcholu # (nikdy nepřiléhají dva pravé kvadranty k sobě). # Pokud se posouváme svisle, naopak se levo/pravost zachovává. if dir[0]: adj_pos[0] = 1 - pos[0] # Pro svislou pozici analogicky. if dir[1]: adj_pos[1] = 1 - pos[1] # pro odvážné: adj_pos = [1-coord if delta else coord for (coord, delta) in zip(pos, dir)] neigh = parent_neigh.children[tuple(adj_pos)] else: neigh = parent_neigh node.S[dir] = neigh if neigh and (not node.children) and (not neigh.children): # Oba sousedící vrcholy jsou listy => objevili jsme novou hranu # grafu sousednosti. Přidáme ji v obou směrech. node.neighs.add(neigh) neigh.neighs.add(node) for pos, child in node.children.items(): find_neighbours(child, node, pos) def find_leaves(node): """Vrať seznam všech listů ve stromě.""" if node.children: ret = [] for child in node.children.values(): ret += find_leaves(child) return ret else: # `node` je list return [node] def component_size(node, color): """Najdi komponentu souvislosti obsahující node, omezuje se na vrcholy dané barvy, a vrať její velikost. Pokud daná komponenta byla již navštívena, vrať 0.""" stack = [node] # zásobník pro DFS area = 0 while stack: node = stack.pop() if node.color != color: continue if node.visited: continue node.visited = True area += node.area stack += node.neighs return area code = input() idx = 0 # aktuální pozice v kódu tree = parse() find_neighbours(tree) leaves = find_leaves(tree) add_areas(tree, 4**get_depth(tree)) max_size = 0 for leaf in leaves: comp_size = component_size(leaf, 0) max_size = max(max_size, comp_size) print(max_size)