Romanko, ako správny maturant, využil Vianočné prázdniny naplno. Posledný týždeň školy mu síce všetci učitelia pripomínali, ako dôležité je sa cez prázdniny venovať štúdiu, ale však čo – na to bude dosť času neskôr – pred Vianocami sa predsa ide nakupovať! No a po Vianociach si predsa tiež Romanko nebude kaziť náladu školou. Oveľa príjemnejšie je cez deň spať a v noci hrať počítačové hry. A po Silvestri? To je predsa perfektný týždeň na lyžovačku!
Na konci prázdnin si teda Romanko po veľmi "produktívne" strávenom čase pozrel, aké domáce úlohy to vlastne cez ne mal stihnúť. Otvoril si svoj zápisníček a so zhrozením zistil, že je tam práce skoro na tri týždne (aká to náhoda, všakže?). Najťažšou úlohou je veľký projekt z informatiky. Čo teraz bude robiť? Ak svoj projekt z informatiky nespraví, bude mať len dve možnosti: odísť zo školy a zamestnať sa ako vývojár webových stránok, alebo dajako uprosiť svoju učiteľku informatiky, aby ho nechala prejsť s odretými ušami. V momentálnom stave však, napriek Romankovým vynikajúcim presvedčovacím schopnostiam, jeho projekt určite stačiť nebude.
Romanko si však spásonosne spomenul, že kedysi, keď namiesto vypracovávania dôležitých esejí riešil programátorské úlohy na SPOJi, mu pán profesor Demáček za každú vyriešenú úlohu napísal na vyvesenú tabuľu malé, bezvýznamné plus. Tieto pluská ale občas neboli vôbec malé (čím ťažšiu úlohu Romanko vyriešil, tým väčšie plus mu profesor napísal) a nemuseli by byť ani bezvýznamné – mohol by predsa svoju učiteľku presvedčiť, aby mu ich uznala ako bonusové body z programovania!
Utekal teda do Školského Výpočtového Laboratória a uprel pohľad na tabuľu s pluskami. Och, nie! Nejaký darebák ju nenávratne počmáral. Čo bude teraz robiť? Počmárané pluská mu učiteľka v žiadnom prípade neuzná! So slzami na krajíčku a niektorými cezeň si skleslo sadol na zem a prehodnocoval svoje životné rozhodnutia. Našťastie ste práve okolo Romanka išli vy. Vypočuli ste si jeho príbeh, a dali ste mu návrh – ak vám dá zvyšné horalky, ktoré ušetril pri podplácaní trpaslíkov, tak mu pomôžete spočítať, koľko plusiek ostalo na tabuli nepočmáraných. Romanko samozrejme nemal príliš na výber, a pristúpil na vaše podmienky.
Úloha
Tabuľa v Školskom Výpočtovom Laboratóriu je štvorcová a má stranu dĺžky \(n\) milimetrov. Pre potreby úlohy si ju vieme predstaviť ako mriežku pozostávajúcu z \(n\) riadkov. V každom riadku je \(n\) štvorčekových políčok o veľkosti \(1 \times 1\) milimeter a každé z týchto políčok môže byť popísané alebo nepopísané.
Nepočmárané plus veľkosti \(v\) je štvorec so stranou dĺžky \(2v + 1\) milimetrov, v ktorom je celý stredný riadok a stredný stĺpec popísaný, a všetky ostatné políčka v ňom sú nepopísané.
Za nepočmárané plus veľkosti \(v\) dostane Roman \(v\) bonusových bodov.
Každé nepočmárané plus veľkosti aspoň 2 obsahuje vo svojom strede menšie nepočmárané pluská. Za tieto menšie pluská však Roman už ďalšie body pochopiteľne nedostane.
Roman vám ukázal počmáranú tabuľu. Pomôžte mu zistiť, koľko bonusových bodov vie získať!
Formát vstupu
V prvom riadku je číslo \(n (1 \leq n \leq 2\,000)\) – veľkosť tabule. Nasleduje \(n\) riadkov, každý presne \(n\) znakov dlhých – obrázok tabule. Znak
'#' predstavuje popísané políčko, znak
'.' nepopísané políčko.
Formát výstupu
Vypíšte jediné číslo – počet bonusových bodov, ktoré Roman vie získať, a znak nového riadku.
Príklad
Input:
3 .#. ### .#.
Output:
1
Takto vyzerá nepočmárané plus veľkosti 1. Romanko zaň dostane 1 bonusový bod.
Input:
8 ...#.... ...#.... ...#.... ######## ...#.... ...#..#. ...#.### ...#..#.
Output:
3
V pravom dolnom rohu je nepočmárané plus veľkosti 1. Štvorec s ľavým horným rohom na druhom políčku druhého riadku a s pravým dolným rohom na 6. políčku 6. riadku je nepočmárane plus veľkosti 2. Romanko teda vie získať najviac \(1+2=3\) body.
Štvorec s rohmi na políčkach \((1,1)\) a \((7,7)\) je počmárané plus, keďže v pravom dolnom rohu mu zavadzajú popísané políčka menšieho pluska.
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.