L - LED

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Úloha

Valentín sa rozhodol ozdobiť si dom novým osvetlením. Vyhliadol si tvar, ktorý by tam chcel mať. Ale keď zistil, koľko by ho takéto originálne svetlo stálo a spotrebovalo elektriny, rozhodol sa, že si vyrobí taketo svetlo sám a použije na to LED pásy. Dal si u svojho dobrého kamaráta Ferka vyrobiť daný tvar. Teraz by ho chcel vyplniť LED diódami tak, aby mohol vysvietiť celé vnútro, ale aj vytvoriť efekt postupného svietenia (zľava doprava - po stĺpcoch, resp. zhora dole - po riadkoch). Pre daný tvar a zadané niektoré body určujúce vnútro (ktoré chce osvetliť) nájdite jeho vyplnenie LED pásikmi.K dispozícií má dostatočne dlhý pás, ktorý treba rozstrihať a poukladať do vnútra po riadkoch alebo po stĺpcoch. Pomôžte mu určiť, koľko takýchto rozstrihnutí minimálne potrebuje.

Vstup

Prvý riadok obsahuje rozmery štvorcovej dosky (z ktorej bol daný tvar vytvorený), počet riadkov 3 ≤ R ≤ 1 000 a počet stĺpcov 3 ≤ S ≤ 1 000. Ďalších R riadkov obsahuje S znakov. Hranica tvaru je označená znakom 'x', prázdne políčko '.' a vnútorný bod '+'. Môžete predpokladať, že hranica tvaru je dobre zadaná - t.j. postupným prechádzaním z vnútorného bodu jedným zo štyroch smerov (hore, dole, vľavo, vpravo) sa vždy dostaneme k hranici tvaru. V každej oblasti, ktorá má byť vyplnená, je práve jeden vnútorný bod.
Na výpočet je možné použiť riadkové 4-smerové semienkové vypĺňanie (algoritmus počítačovej grafiky), ktorého princípom je vyplnenie celého úseku v tomto riadku a potom do každého nevyplneného úseku nad (aj pod) práve vyplneným úsekom vloží jedno semienko.

Skonzumuj semienko (bod vnútra) [x, y]
Nájdi prvú hranicu naľavo xL a napravo xR od semienka v danom riadku
Vyplň nájdený úsek v danom riadku (od [xL, y] do [xR, y]).
Do každého súvislého úseku nevyplnených bodov v riadku nad (od [xL,y-1] do [xR, y-1]) vlož jedno semienko
Do každého súvislého úseku nevyplnených bodov v riadku pod (od [xL,y+1] do [xR, y+1]) vlož jedno semienko

Analogicky je možné aplikovať tento algoritmus aj pre stĺpce.

Výstup

Minimálny počet rozstrihnutí nekonečného LED pásu na menšie pásiky, pri ktorom budú všetky vnútorné body pokryté LED diódami, pričom tieto pásiky je možné ukladať len rovnobežne (t.j. buď všetky zvislo alebo všetky vodorovne).

Príklad

Vstup:

8 5
.xxx.
x...x
x.+.x
.xxx.
x...x
x.+.x
x...x
.xxx.

Výstup:

Vysvetlenie:

Pri umiestnení pásikov zvislo (obr. vľavo) potrebuje 6 pásikov (2 pásiky do každého stĺpca), v prípade umiestnenia vodorovne mu stačí odstrihnúť 5 pásikov.

 xxx        xxx 
x135x      x111x
x135x      x222x
 xxx        xxx 
x246x      x333x
x246x      x444x
x246x      x555x
 xxx        xxx

21 Domáce 1