#!/usr/bin/python # coding: utf-8 import sys # Načtení vstupu. Funkce map je použitá místo delšího for cyklu. vstup = map(lambda radek: map(lambda znak: znak == '#', radek.rstrip()), sys.stdin.readlines()) # Odšachovnicování vzorů ‒ na lichých pozicích znegujeme for i in range(0, len(vstup)): radek = vstup[i] for j in range(0, len(radek)): if (i + j) % 2 == 1: radek[j] = not radek[j] def max_ctverec(vstup): """ Určí maximální čtverec složený ze samých True. Vrací v podivném tvaru ((velikost, x), y), kde x a y jsou souřadnice pravého dolního rohu počítáno od 1. Divný formát je vedlejší efekt implementace a je jednodušší si ho rozebrat na straně volajícího, než generovat rozumný. """ v = len(vstup) s = len(vstup[0]) # Přidej horní rámeček z nul. velikosti = [ [ 0 ] * (s+1) ] for i in range(0, v): # Kousek levého rámečku velikosti.append( [ 0 ] ) for j in range(0, s): if vstup[i][j]: # Koukni na okolní políčka. # Pozor na posun indexů kvůli rámečku z nul. ostatni = min(velikosti[i][j], velikosti[i][j+1], velikosti[i+1][j]) velikosti[i+1].append(ostatni + 1) else: # Tady čtverec není velikosti[i+1].append(0) # V podstatě jen nalezení maxima v dvourozměrném poli, ale přibalí ke každé hodnotě, kterou # zkoumá, její souřadnice. Max porovnává lexikograficky, tedy hlavní je pro něj velikost čtverce. return max(map(lambda radek, cislo: (max(zip(radek, range(0,s+1))), cislo), velikosti, range(0, v+1))) zlute = max_ctverec(vstup) # Prohodíme žluté a červené vstup = map(lambda radek: map(lambda policko: not policko, radek), vstup) cervene = max_ctverec(vstup) # Rozebrání výsledku ((velikost, sloupec), radek) = max(zlute, cervene) # Konverze souřadnic na levý horní roh. print("Čtverec velikosti " + str(velikost) + " s levým horním rohem na řádku " + str(radek - velikost + 1) + " a sloupci " + str(sloupec - velikost + 1))