Državno natjecanje 2018. godine za 3. i 4. razred Srednje Škole - 2. zadatak - Dan 1

Nakon što su autori pripremili zadatke za natjecanje, odlučili su pronaći Krešu koji po običaju luta hotelom kako bi s njim otišli na večeru. Nakon dugog traganja pronašli su ga u prostoriji za natjecanje. Osim Kreše u prostoriji su vidjeli i ogroman nered - hrpu prevrnutih monitora te lopticu koja se odbija od zidova. Organizatori su ga upitali što se dogodilo na što je on, kako bi prikrio što je napravio, odgovorio zadatkom umjesto objašnjenjem:

“Zamislite Mirka kako se nalazi unutar pravokutne prostorije podijeljene na N x M polja veličine 1 x 1 metar. Slovom ‘o’ opisujemo polje u čijem središtu se nalazi Mirko, prazna polja opisujemo točkom (znak ‘.’), a polja u čijem središtu se nalazi stol s monitorom opisujemo jednim od znakova ‘|’ ili ‘-’, ovisno o položaju monitora.

Mirko je nadljudskom snagom bacio lopticu u smjeru sjeveroistoka u visini monitora. U trenutku u kojem je loptica udarila u monitor ili u zid prostorije, odbila se, tj. promijenila smjer leta za 90 stupnjeva u stranu u koju može nastaviti letjeti, s iste strane monitora ili zida s koje se nalazila prije sudara. Pri udarcu loptice, monitor se prevrće i pada sa stola. U slučaju da loptica udari u kut prostorije, mijenja smjer leta za 180 stupnjeva, a ako dođe do pozicije na kojoj se nalazi Mirko, on se izmiče kako ga ne bi pogodila. Na slici je prikazano odbijanje loptice u prostoriji iz prvog primjera niže:

Rekonstruirajte put loptice tako što ćete za svaki monitor ispisati u kojoj sekundi je prevrnut, ako je loptica putovala brzinom od jednog polja u sekundi. Pretpostavite da loptica nikad nije prestala letjeti.”

Pomozite autorima riješiti Krešin zadatak kako bi ga mogli uvaliti natjecateljima na prvi dan natjecanja.

ULAZNI PODACI

U prvom retku nalaze se prirodni brojevi N i M (1 ≤ N, M ≤ 1500), dimenzije prostorije.

U sljedećih N redaka nalazi se po M znakova koji opisuju odgovarajuća polja prostorije kao u tekstu zadatka. Točno jedan od znakova bit će malo slovo ‘o’ (početna pozicija loptice).

IZLAZNI PODACI

Ispišite N redaka u kojima se nalazi po M brojeva koji odgovaraju poljima prostorije. Za svaki srušeni monitor, na njegovoj poziciji ispišite broj sekundi od početka leta nakon kojih je monitor srušen. Na svim ostalim pozicijama (uključujući monitore koji nisu srušeni) ispišite broj 0.

PRIMJERI TEST PODATAKA

ulaz

2 2
.-
o|

izlaz

0 1
0 2

ulaz

3 2
||
||
o|

izlaz

2 3
4 1
0 5

ulaz

3 3
-.-
.|.
o..

izlaz

2 0 0
0 1 0
0 0 0

Objašnjenje

Pojašnjenje prvog primjera: Pogledati sliku iz teksta zadatka