Državna razina / Primjena algoritama OŠ 2021. / Osnovna škola (7. 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 lice 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 licem:

• Slika, da bi bila lice, 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 te je jednako udaljen od lijevog i desnog ruba tablice. Ako je broj stupaca tablice neparan, nos počinje s jednim zauzetim poljem, a inače s dva. Svaki sljedeći redak ima jedno zauzeto polje više prema lijevo i 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 lice.

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

Primjeri slika koje sadrže lice:

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 (treba početi s jednim zauzetim poljem).

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 je pravog oblika, ali nije jednako udaljen od oba ruba tablice. Postoji zauzeto polje koje nije dio ni jedne komponente.

Mirko je dobio zadatak odrediti 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 lice, 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: Sva uvjeti za lice 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.