Alliances
U jednoj zemlji iz bajke, nalazi se otok pravokutnog oblika. Otok zamišljamo kao pravokutnu mrežu dimenzija R × []. Za dva polja kažemo da su susjedna ako dijele stranicu. Četiri dominantne vrste na otoku su: vilenjaci (elves), ljudi (humans), patuljci (dwarves) i hobiti (hobbits). Na nekim poljima nalaze se naselja, dok su preostala polja nenaseljena. U svakom naselju živi jedna od četiri vrste. Dva susjedna naselja mogu sklopiti vojni pakt kako bi se osjećala sigurnije. Pakt je simetričan, tj. obvezuje obje strane. Vaš je zadatak da sklopite vojne paktove između susjednih naselja, tako da su zadovoljeni
sljedeći uvjeti:
• Naselje u kojem žive vilenjaci mora sklopiti točno jedan pakt.
• Naselje u kojem žive ljudi mora sklopiti točno dva pakta i to u okomitim smjerovima.
Drugim riječima, dva naselja s kojima će ovo naselje sklopiti pakt ne smiju biti na suprotnim stranicama kvadrata.
• Naselje u kojem žive patuljci mora sklopiti točno tri pakta.
• Naselje u kojem žive hobiti mora sklopiti točno četiri pakta.
Ovi uvjeti moraju vrijediti bez obzira na položaj naselja na otoku. Na primjer, ako se naselje patuljaka nalazi na obali tada mora sklopiti pakt sa sva tri susjeda, a ako se nalazi na samom kutu, tada nije moguće zadovoljiti uvjete.
Vaš je zadatak da na temelju opisa otoka odredite je li moguće oformiti paktove tako da su zadovoljene potrebe svakog naselja na otoku. Ako je to moguće napraviti, potrebno je odrediti jednu takvu konfiguraciju. Ako je to moguće napraviti na više načina, odaberite bilo koji.
Bodovanje i ograničenja
U svim test podacima vrijedi 1≤ R, C ≤ 70.
Svaki od sljedećih R redova sadrži C brojeva između 0 i 4:
• 0 označava nenaseljeno polje,
• 1 označava naselje u kojem žive vilenjaci,
• 2 označava naselje u kojem žive ljudi,
• 3 označava naselje u kojem žive patuljci,
• 4 označava naselje u kojem žive hobiti.
(Primijetite da broj također označava broj paktova koje naselje mora sklopiti sa susjednim
naseljima.)
(točka). Ako je polje naseljeno, tada se u centru matrice mora nalaziti znak O (veliko slovo O) koji predstavlja naselje. U smjerovima koji pokazuju prema naseljima s kojima je sklopljen pakt mora se nalaziti znak X (veliko slovo X). Ostatak matrice mora biti popunjen znakovima . (točka). Sljedeća slika prikazuje sve dozvoljene konfiguracije, za svaki pojedini tip naselja:
[c]3 4
2 3 2 0
3 4 3 0
2 3 3 1
izlaz:
............
.OXXOXXO....
.X..X..X....
.X..X..X....
.OXXOXXO....
.X..X..X....
.X..X..X....
.OXXOXXOXXO.
............ Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.