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

Sokoban

To je „off-line naloga“. Na tej spletni strani je objavljen opis naloge in testni primeri. Svoje rešitve lahko pošlješ prek obrazca na tej strani kadarkoli do vključno 24. marca 2023 (dan pred tekmovanjem).

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.

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). 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.

Naslednji sliki kažeta primera obeh načinov premikanja zabojev. Temno modra polja so zidovi, sinje modra so odlagališča, bela so ostala prehodna polja; rdeči kvadratki so zaboji. Na prvi sliki se skladiščnik premakne gor in rine zaboj pred sabo, na drugi sliki pa se premakne v desno in prestavi zaboj na svoj dosedanji položaj:



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.

Obrazec za oddajo rešitev

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

Datoteka s tvojo rešitvijo:

Najboljše doslej oddane rešitve

Prikaži podrobno tabelo rezultatov po posameznih testnih primerih.

Skupni seštevek

V skupnem seštevku se za vsakega tekmovalca seštejejo njegove točke z vseh testnih primerov.

Ime in priimekRezultat
Luka Stražišar10

[H kazalu. | Na vrh te strani. | Imate vprašanje ali komentar?]