B - Letokruhy

Č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 ]

Dentrochronológia je vedná disciplína dátovania časových udalostí, založená na analýze letokruhov stromov. Letokruh je prírastok dreva vytvorený v priebehu jedného vegetačného obdobia. Počet letokruhov na radiálnom reze tak zodpovedá veku daného stromu. Letokruh je spravidla rozdelený na dve časti. Jarné drevo je zvyčajne svetlejšie, letné drevo je tmavšie a tvrdšie. Dr. Sparks je uznávaný dentrochronológ, no najčastejším problémom v jeho práci je určenie počtu letokruhov.

Úloha

Daný je čiernobiely obrázok prierezu stromu, kde čierna farba označuje tmavšie (letné drevo). Napíšte program, ktorý z tohto obrázku spočíta počet letokruhov. Predpokladajte, že každá dvojica (aj uhlopriečkou) susediacich čiernych bodov patrí do toho istého letokruhu.

Vstup

Prvý riadok vstupu určuje veľkosť obrázka a teda obsahuje dve kladné, medzerou oddelené celé čísla N, M (1≤N,M≤500). Ďalej bude nasledovať N riadkov, z ktorých každý obsahuje M znakov '0' alebo '1'. Hodnoty '1' prestavujú tmavšie drevo a teda určujú letokruhy.

Výstup

Výstupom má byť jediný riadok (ukončený znakom konca riadku) určujúci počet letokruhov na danom obrázku.

Príklad 1

Vstup:

Výstup:

Príklad 2

Vstup:

9 12
001111111000
010000000110
100011110010
101100001001
101001001001
100100001001
010011100010
001000000100
000111111000

Výstup:

06 Finále 1