Sokoban

Srednješolsko tekmovanje ACM iz računalništva in informatike

Sokoban

Podroben opis naloge

Pri tej nalogi se bomo ukvarjali z malo spremenjeno različico znane igre Sokoban. Dana je karirasta mreža, ki predstavlja tloris skladišča. Vsaka celica v mreži je bodisi prehodna bodisi zazidana. Na nekaterih prehodnih celicah stojijo zaboji (največ po en zaboj na celico). Poleg tega so na nekaterih prehodnih celicah odlagališča. Število odlagališč in zabojev je enako.

Na eni od prehodnih celic (taki, kjer ni zaboja) stoji skladiščnik, ki se lahko sprehaja po mreži; v vsakem koraku se lahko premakne za eno celico gor, dol, levo ali desno, seveda le po prehodnih celicah (ne pozabimo, da med slednje štejejo tudi odlagališča).

Skladiščnik lahko tudi premika zaboje, in sicer na naslednja dva načina: (1) ob premiku lahko zaboj rine pred sabo, vendar le, če je naslednja celica v tisti smeri prehodna in brez zaboja; (2) lahko pa zaboj s celice, na katero bi se rad premaknil, prestavi na celico, na kateri zdaj stoji skladiščnik.

(Pozor: naša naloga se tu malo razlikuje od originalne različice igre Sokoban — tam namreč premiki tipa (2) niso možni.)

Skladiščnik se ne sme premakniti ven iz mreže in tudi ne sme riniti zabojev ven iz mreže.

Naslednje slike kažejo primer skladišča in vseh možnih premikov, ki jih lahko skladiščnik takrat naredi. Temno modra polja so zidovi, sinje modra so odlagališča, bela so ostala prehodna polja; rdeči kvadratki so zaboji.

Tvoja naloga je spraviti čim več zabojev na odlagališča (pri tem ni pomembno, kateri zaboj stoji na katerem odlagališču), pri tem pa izvesti čim manj premikov zabojev. Ko zaboj premakneš na odlagališče, ni nujno, da tam tudi ostane; lahko ga kasneje premakneš stran z njega. Vse, kar šteje, je to, koliko zabojev stoji na odlagališčih v končnem stanju mreže, po vseh premikih.

Ocenjevalni program

Lahko si preneseš izvorno kodo programa, s katerim bomo ocenjevali prejete rešitve: Rtk23Sokoban.cpp.

Na voljo je tudi prevedena različica ocenjevalnega programa (za Windows).

Oblika vhodne datoteke

Pri tej nalogi so vsi testni primeri podani v eni vhodni datoteki. V prvi vrstici vhodne datoteke je niz z imenom naloge (Sokoban), v drugi pa število testnih primerov (T). Sledijo testni primeri, pred vsakim od njih pa je še ena prazna vrstica.

Vsak testni primer se začne z vrstico, ki vsebuje številko tega testnega primera (od 1 do T). Sledi vrstica z dvema številoma: w (širina mreže) in h (višina mreže). Sledi h vrstic, ki podajajo začetno stanje mreže; v vsaki od njih je w znakov, ki predstavljajo stanje celic v tej vrstici mreže. Možni znaki so naslednji:

Primer: če bi imeli en sam testni primer, in sicer tistega iz slik v opisu naloge zgoraj, bi bila vhodna datoteka lahko takšna:

Sokoban
1

1
7 6
#######
#.O.#O#
#.Z#.O#
#.SZZ.#
#.#####
####...

V resnici je pri tej nalogi 30 testnih primerov.

Oblika izhodne datoteke

Oddaš lahko poljubno število izhodnih datotek s svojimi rešitvami. Pri tem vsaka izhodna datoteka vsebuje rešitve za enega ali več testnih primerov. Če za isti testni primer oddaš več rešitev, bomo pri ocenjevanju upoštevali najboljšo med njimi.

Oblika posamezne izhodne datoteke je naslednja:

V prvi vrstici naj bo koda, ki si jo dobil(a) ob registraciji in iz katere je razvidno, da si rešitev res poslal(a) ti, ne pa kdo drug. V drugi vrstici naj bo ime naloge (Sokoban). Sledijo naj tvoje rešitve za enega ali več testnih primerov.

Vsaka rešitev se začne s prazno vrstico. Sledi naj vrstica, ki vsebuje številko testnega primera (od 1 do T), na katerega se ta rešitev nanaša. V drugi vrstici naj bo celo število (recimo k), ki pove, koliko korakov izvede skladiščnik pri tvoji rešitvi. Veljati mora 0 ≤ k ≤ 107. V tretji vrstici naj bo niz 2k znakov, ki po vrsti opisujejo izvedene korake skladiščnika v tvoji rešitvi.

Vsak korak naj bo predstavljen z dvema znakoma. Prvi znak naj pove, za kakšno vrsto koraka gre: 0 = skladiščnik se premakne na polje, kjer ni zaboja; 1 = skladiščnik rine zaboj pred sabo; 2 = skladiščnik se premakne na polje, kjer je bil zaboj, le-tega pa prestavi na polje, kjer je pred tem premikom stal skladiščnik sam. Drugi znak naj pove, v katero smer se je skladiščnik pri tem premaknil: G = gor, D = dol, L = levo, R = desno.

Primer: če bi bila naša uporabniška koda enaka 123456 in bi obstajal prvi testni primer, kakršen je prikazan zgoraj, bi lahko oddali spodnjo izhodno datoteko. 

123456
Sokoban

1
17
1G0D2R1R0G0R2D1G0L0D0L2L1R1R0G0R2D

To je veljavna rešitev, ki v 17 korakih spravi vse tri zaboje na odlagališča. Pri tem izvede 9 premikov zabojev. Naslednja slika kaže začetno in končno stanje mreže pri tej rešitvi:

Ocenjevanje

Boljša je tista rešitev, ki spravi na odlagališča več zabojev. Če sta dve rešitvi po tem kriteriju enaki, je boljša tista, pri kateri skladiščnik manjkrat premakne zaboje (štejejo tako premiki tipa 1 kot premiki tipa 2). Če sta rešitvi tudi po tem kriteriju enaki, je boljša tista z manjšim skupnim številom korakov. (Če se ujemata tudi po tem, veljata rešitvi za enako dobri.)

Rešitev, ki ne ustreza zgoraj opisanim pravilom za obliko izhodne datoteke ali pa ki vsebuje kakšen nedovoljen premik (npr. če se skladiščnik zaleti v zid ali pa skuša riniti zaboj v polje, ki ni prazno ipd.), je neveljavna in se ne bo upoštevala.

Vhodni podatki

Registracija

Preden lahko oddajaš svoje rešitve, se prijavi prek spodnjega obrazca. Dodelili ti bomo enolično uporabniško kodo, ki jo boš potreboval(a) za pripravo svojih izhodnih datotek.

Opomba: pri tej nalogi lahko sodeluje kdorkoli, ne glede na starost, izobrazbo, itd. Objavili bomo rezultate vseh tekmovalcev, za morebitne praktične nagrade pa pridejo v poštev le srednješolci/ke in študentje/ke.

Ime in priimek: *
e-mail: *
Šola:
Letnik:
Mentor:
 

Obrazec za oddajo rešitev

(Oddaja rešitev je možna do vključno 24. marca 2023.)

Datoteka s tvojo rešitvijo:

[Nazaj na glavno stran. | Na vrh te strani. | Imate vprašanje ali komentar?]