Državno natjecanje 2014. / Osnovna škola (7. razred) - 2. zadatak

Pokraj Primoštena maleni je otok koji možete vidjeti iz hotela u kojemu se nalazite, a do njega se u toplijim mjesecima lako može i doplivati.

Nažalost, otočić je slabo prohodan. Država je odlučila otočić učiniti pristupačnijim tako da na njemu napravi staze.

Otok zamišljamo kao matricu od R x S znakova.

Na početku, svi znakovi su '.' (točke), a tvoj je zadatak u nju upisati staze – polja gdje se one nalaze označit ćeš znakom '#' (ljestve).

Stazama se možemo kretati koracima gore, dolje, lijevo i desno. Staze koje postaviš moraju zadovoljiti sljedeće uvjete:

1. Povezanost: iz svakog polja staze moguće je koracima doći u svako drugo polje staze.
2. Nema ciklusa: da se na otoku nitko ne bi izgubio, ne smijemo dopustiti da se staza "zavrti u krug". Preciznije, ako krenemo stazom iz nekog polja i ne vraćamo se istim putem, ne možemo ponovno doći u početno polje.

Primjer. Ispod vidimo tri konfiguracije staza.

Prva je dozvoljena (povezana je i nema ciklusa). Druga je nedozvoljena jer sadrži ciklus od četiri polja, a nije ni povezana! Treća je nedozvoljena jer sadrži ciklus od dvanaest polja.

Staze trebaju sadržavati što više polja odluke.

Polje staze zovemo poljem odluke ako ima barem tri susjeda (susjedna polja staze u smjerovima gore, dolje, lijevo, desno).

Na primjer, u prvoj konfiguraciji iznad, samo je polje u prvom retku i drugom stupcu polje odluke.

U pojedinom test podatku, ako tvoje rješenje sadrži K polja odluke, a autorovo M, tada za taj test podatak osvajaš

10 * (K / M)

bodova (od mogućih 10).

Ako ovaj broj nije cijeli, zaokružuje se na prvi manji cijeli broj.

Oprez: ako tvoje rješenje ne zadovoljava tražene uvjete, osvaja nula bodova bez obzira na broj polja odluke!

ULAZNI PODATCI

U prvom i drugom retku nalaze se, redom, prirodni brojevi R i S (2 ≤ R, S ≤ 100), dimenzije otoka.

IZLAZNI PODATCI

Ispiši R redaka od po S znakova koji predstavljaju tvoj izgled otoka sa stazama

PRIMJERI TEST PODATAKA

Ulaz

5
5

Izlaz

.###.
#.#.#
#####
#.#.#
.###.

komentar

Ovaj otok sadrži 5 polja odluke.

Tvoj izlaz uspoređuje se s ovim po formuli iz teksta zadatka.