Državno natjecanje 2019. / Osnovna škola (7. razred) - 3. zadatak

Mirko je za rođendan dobio slagalicu koja se sastoji od manjih zasebnih komada.

Svaki komad slagalice opisujemo kao neki broj međusobno povezanih kvadratića iste veličine.

Za neka dva kvadratića kažemo da su povezana ako postoji niz kvadratića koji započinje jednim od njih, a završava drugim te da za svaki kvadratić u nizu vrijedi da dijeli stranicu s prethodnim iz niza

Cilj slagalice je rasporediti komade jedan do drugog tako da oni tvore pravokutnik dimenzija NxM.

Komade slagalice prilikom slaganja Mirko ne smije rotirati niti okretati.

Mirko je započeo slagati slagalicu, no nažalost mu se čini da je slagalica neispravna, tj. čini mu se da nedostaju neki komadi ili da postoje komadi koji su višak.

Zato treba tvoju pomoć.

On će opisati izgled do sada složene slagalice kao tablicu nula i jedinica dimenzija NxM gdje jedinica predstavlja kvadratić na koji je već stavio neki komad slagalice, a nula kvadratić kojeg tek treba popuniti komadom slagalice.

Međusobno povezani skup neprekrivenih kvadratića (oni predstavljeni nulom) Mirko naziva rupom. Unutar rupa se neće nalaziti popunjeni kvadratić.

Mirko će ti također opisati izgled K komada slagalice koji su mu preostali.

Svaki komad će opisati kao tablicu dimenzija 5x5 nula i jedinica, gdje kvadratići u koje je upisana jedinica predstavljaju komad slagalice.

Svi komadi slagalice će biti takvi da stanu unutar tablice dimenzija 5x5. Komadi slagalice će biti međusobno različiti te neće sadržavati rupe.

Mirka sada zanima kako bi izgledala slagalica kada bi se popunile one rupe za koje je potreban točno jedan komad slagalice da ju u cijelosti ispuni.

Pomozi Mirku i ispiši izgled slagalice nakon što se popune te rupe.

Test podaci će biti takvi da je rješenje jedinstveno.

ULAZNI PODATCI

U prvom retku nalaze se prirodni brojevi N i M (3 ≤ N, M ≤ 50), iz teksta zadatka.

U idućih N redaka nalaze se nizovi duljine M koji se sastoje od nula i jedinica, a opisuju izgled do sada složene slagalice.

U idućem retku nalazi se prirodan broj K (1 ≤ K ≤ 15), broj iz teksta zadatka.

U idućih 5 * K*** redaka nalaze se nizovi duljine 5 koji se sastoje od nula i jedinica, a opisuju neiskorištene komade slagalice.

IZLAZNI PODATCI

U N redaka potrebno je ispisati niz duljine M koji se sastoji od nula i jedinica, a predstavlja konačni izgled slagalice nakon postavljanja onih komada slagalice koji savršeno ispunjavaju rupe.

PRIMJERI TEST PODATAKA

Ulaz

5 9
101111111
000011001
100111001
101111110
111111100
4
01000
11110
01100
01000
00000
00000
00110
00100
00000
00000
00001
00000
00000
00000
00000
00000
00010
00110
00000
00000

Izlaz

111111111
111111001
111111001
111111111
111111111

Objašnjenje

Opis prvog primjera: Prvi komad slagalice možemo staviti u najljeviju rupu, drugi bi komad mogli staviti u drugu rupu (onu oblika kvadrata dimenzije 2x2), no tu rupu ne bi u cijelosti ispunio pa drugi komad ne možemo iskoristiti.

Rupu u dolje desnom kutu možemo savršeno ispuniti četvrtim komadom slagalice.

Također, drugu bismo rupu mogli savršeno ispuniti ako iskoristimo drugi i treći komad slagalice zajedno, no Mirko želi da popunimo one rupe koje možemo savršeno popuniti pomoću samo jednog komada pa će druga rupa ostati neispunjena.

Ulaz

4 4
0111
1011
1100
1000
2
00000
00000
00110
01110
00000
00000
00000
11000
00000
00000

Izlaz

0111
1011
1111
1111

Objašnjenje

Opis drugog primjera: Prvi komad slagalice savršeno pristaje u rupu koja se nalazi u dolje desnom kutu slagalice. Ne postoji komad slagalice koji savršeno pristaje u preostale dvije rupe.