Državna razina / Primjena algoritama OŠ 2021. / Osnovna škola (8. razred) - 2. zadatak

Mirko se zaposlio kao programer u jednoj poznatoj firmi. Već prvi dan ga je dopao ozbiljan zadatak. Treba napraviti program koji prepoznaje smajlić na zadanoj slici.

Sliku možemo predstaviti kao tablicu veličine N redaka i M stupaca, a svako polje može biti ili prazno ili popunjeno. Mirko je dobio neka pravila koja slika mora zadovoljavati da bi se smatrala smajlićem:

• Slika, da bi bila smajlić, mora imati određene komponente, a to su: dva oka, nos i usta, poredane tim redom odozgo prema dolje.

• Oči su dva kvadrata jednake veličine sa stranicama paralelnim s rubovima tablice. Kvadrati se ne dodiruju te su na istoj visini (počinju i završavaju u istim redovima tablice). Lijevi kvadrat je od lijevog ruba tablice udaljen jednako kao i desni kvadrat od desnog ruba.

• Nos je trokutastog oblika, a započinje s jednim zauzetim poljem u središnjem stupcu tablice. Ako postoje dva središnja stupca (kada je broj stupaca tablice paran), onda nos počinje u onom lijevom. Svaki sljedeći redak ima jedno zauzeto polje više prema desno. Također, mora postojati barem jedan prazan redak između očiju i nosa.

• Usta su uzastopni niz zauzetih polja u istom retku te su jednako udaljena od lijevog i desnog ruba tablice. Također, mora postojati barem jedan prazan redak između nosa i usta.

• Ako postoji i jedno zauzeto polje koje nije dio neke komponente, slika ne sadrži smajlić.

• Rub tablice (prvi i zadnji redak i stupac) mora biti prazan.

Primjeri slika koje sadrže smajlić:

Lijeva slika ne zadovoljava više pravila: Rub tablice nije prazan. Ne postoji prazan redak između očiju i nosa. Nos je krivog oblika.

Usta nisu jednako udaljena od lijevog i desnog ruba tablice i ne čine uzastopan niz zauzetih polja u istom retku.

Desna slika također ne zadovoljava više pravila: Oči nisu jednake veličine, a i dodiruju se. Nos i usta su dani obrnutim redoslijedom.

Nos započinje u desnom središnjem stupcu umjesto u lijevom. Postoji zauzeto polje koje nije dio ni jedne komponente.

Mirko je dobio zadatak da odredi visinu (broj redaka kroz koje se proteže) očiju, visinu nosa te širinu (broj stupaca kroz koje se proteže) usta.

Još se nije snašao na novom poslu pa te moli da napišeš taj program za njega.

Ulazni podaci

U prvom su retku dva prirodna broja N i M (1 ≤ N, M ≤ 1000), brojevi iz teksta zadatka.

U sljedećih N redaka je po M znakova ‘.’ i ‘#’ koji predstavljaju sliku. ‘.’ označava prazno, a ‘#’ zauzeto polje.

Izlazni podaci

Ako slika sadrži smajlić, ispiši tri broja: visinu očiju, visinu nosa te širinu usta, svaki u svom retku. Inače, ispiši -1.

Primjer zadatka

Ulaz

7 5
.....
.#.#.
.....
..#..
.....
..#..
.....

Izlaz

1
1
1

Ulaz

8 6
......
.#..#.
......
..#...
..##..
......
..##..
......

Izlaz

1
2
2

Objašnjenje

Opis drugog probnog primjera: Svi uvjeti za smajlića su ispunjeni, a visina očiju je 1, visina nosa 2 i širina usta 2.

Ulaz

6 5
##.##
##.##
..#..
..##.
.....
#####

Izlaz

-1

Objašnjenje

Opis trećeg probnog primjera: Slika ne zadovoljava sljedeće uvjete: Ne postoji prazan redak između očiju i nosa te rub tablice nije prazan.