Školsko natjecanje 2014. / Osnovna škola (8. razred) - 3. zadatak

Proučavajući mikroskopom razne preparate na satu biologije, Ivica je otkrio novu vrstu bakterije vrlo zanimljivog ponašanja. Naime, ova bakterija ima sposobnost bioluminiscencije tj. može svijetliti. Promatrajući ih malo dulje, Ivica je primijetio neke pravilnosti u njihovu ponašanju.

Preparat na kojem se nalaze bakterije oblika je pravokutnika podijeljenog na kvadrate jednake veličine koje zovemo ćelije. U svakoj od tih ćelija nalazi se točno jedna bakterija. Na početku punog sata svaka bakterija odlučuje hoće li svijetliti ili neće tijekom tog sata. To ovisi o tome koliko je susjednih bakterija oko nje svijetlilo u prijašnjem satu. Ako je barem polovina njoj susjednih bakterija svijetlila, ona će idućih sat vremena također svijetliti, dok u suprotnom neće. Pritom se susjednim bakterijama nekoj bakteriji smatraju one koje se nalaze u ćelijama koje dijele barem jedan zajednički vrh sa ćelijom u kojoj se ta bakterija nalazi (promatraju se, dakle, bakterije u ćelijama susjednima u osam osnovnih smjerova). Primijetite da nemaju sve bakterije osam susjeda, nego ih mogu imati i manje ako se nalaze u ćelijama na rubu preparata.

Neposredno nakon početka punog sata, Ivica je nacrtao kako izgleda preparat. Sada ga zanima kako će on izgledati nakon K sati. Da ne bi morao čekati tako dugo i svakih sat vremena bilježiti promjene, Ivica te moli da odrediš kako će preparat izgledati nakon tog vremena.

Ulazni podaci

U prvome retku nalaze se prirodni brojevi N i M (1 ≤ N, M ≤ 10), broj redaka i stupaca tablice koja predstavlja preparat te prirodni broj K (1 ≤ K ≤ 10), broj sati nakon kojeg Ivicu zanima kako izgleda preparat.

U svakom od sljedećih N redaka nalazi se po M znakova koji predstavljaju tablicu koju je Ivica nacrtao. Znakovi u tablici imaju sljedeće značenje: znak točke (‘.’) - bakterija u toj ćeliji ne svijetli znak ljestvi (‘#’) - bakterija u toj ćeliji svijetli

Izlazni podaci

U svakom od N redaka ispiši po M znakova koji će predstavljati preparat nakon K sati. Tablicu ispiši u istom formatu kako je zadana u ulaznim podacima.

Primjeri test podataka

Ulaz

3 3 1
#..
#.#
.#.

Izlaz

.#.
.#.
#.#

Ulaz

4 5 2
...#.
.##.#
##.#.
#..#.

Izlaz

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

Ulaz

3 2 5
.#
##
..

Izlaz

##
..
##