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

Kratek opis naloge na tej strani.
Podroben opis naloge in oblike vhodnih ter izhodnih datotek.
Vhodne datoteke.
Registracija (preden lahko oddajaš svoje rešitve).
Obrazec za oddajo tvojih rešitev.
Rezultati.
Najboljši doslej oddani rezultati za posamezni testni primer.
Razvrstitev tekmovalcev v skupnem seštevku.

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.

Podrobnejši opis naloge ter vhodnih in izhodnih datotek.
Vhodne datoteke.
Registracija.

Obrazec za oddajo rešitev

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

Najboljše doslej oddane rešitve

Prikaži podrobno tabelo rezultatov po posameznih testnih primerih.

Skrij tabelo rezultatov po posameznih testnih primerih.

Prikazana je najboljša rešitev vsakega uporabnika. Če ima več uporabnikov enako dobre rešitve, so urejeni po času oddaje.

Pri vsakem testnem primeru lahko tekmovalec dobi od 1 do 10 točk, odvisno od svoje uvrstitve (10 za prvo mesto, 8 za drugo, 7 za tretje, . . . , 2 za osmo, 1 za vsa nadaljnja mesta). Kdor za nek testni primer ni oddal nobene veljavne rešitve, dobi pri njem 0 točk.

Pomen stolpcev: w = širina mreže; h = višina mreže; k = število zabojev; O = število zabojev, ki so na koncu na odlagališčih (več je bolje); P = število premikanj zabojev (manj je bolje); K = število vseh korakov (manj je bolje).

Testni primer	w	h	k	Ime	Ocena oddaje			Točke oddaje
Testni primer	w	h	k	Ime	O	P	K	Točke oddaje
1	10	10	5	Luka Stražišar	5	31	128	10
				Mai Rupnik	5	35	83	8
				Brin Blazko	5	39	86	7
				Aljaž Brodar	5	85	458	6
2	9	9	16	Luka Stražišar	16	16	23	10
				Mai Rupnik	16	16	23	10
				Brin Blazko	16	16	23	10
				Aljaž Brodar	16	50	363	6
3	10	10	20	Mai Rupnik	20	6	25	10
				Luka Stražišar	20	6	25	10
				Brin Blazko	20	6	27	7
				Aljaž Brodar	20	22	77	6
4	12	12	9	Luka Stražišar	9	25	69	10
				Mai Rupnik	9	27	54	8
				Brin Blazko	9	33	80	7
				Aljaž Brodar	9	189	802	6
5	13	10	12	Mai Rupnik	12	16	42	10
				Luka Stražišar	12	16	42	10
				Brin Blazko	12	22	50	7
				Aljaž Brodar	12	42	150	6
6	15	12	24	Mai Rupnik	24	8	40	10
				Luka Stražišar	24	8	40	10
				Brin Blazko	24	14	53	7
				Aljaž Brodar	24	130	640	6
7	13	11	17	Luka Stražišar	17	14	40	10
				Mai Rupnik	17	14	42	8
				Brin Blazko	17	36	75	7
				Aljaž Brodar	17	148	838	6
8	16	16	54	Mai Rupnik	54	54	108	10
				Luka Stražišar	54	54	108	10
				Brin Blazko	54	74	132	7
				Aljaž Brodar	54	368	4304	6
9	19	19	48	Luka Stražišar	48	42	82	10
				Mai Rupnik	48	42	88	8
				Brin Blazko	48	86	156	7
				Aljaž Brodar	48	360	2208	6
10	29	17	98	Luka Stražišar	98	212	647	10
				Mai Rupnik	98	234	547	8
				Brin Blazko	98	362	761	7
				Aljaž Brodar	37	1	1	6
11	40	40	15	Luka Stražišar	15	233	911	10
				Mai Rupnik	15	243	642	8
				Brin Blazko	15	287	748	7
				Aljaž Brodar	2	13	64	6
12	40	37	200	Luka Stražišar	200	1353	3317	10
				Mai Rupnik	200	1359	3011	8
				Brin Blazko	200	2083	4804	7
				Aljaž Brodar	1	3	6	6
13	37	40	30	Luka Stražišar	30	767	2091	10
				Mai Rupnik	30	819	1845	8
				Brin Blazko	30	939	2250	7
				Aljaž Brodar	0	6	14	6
14	34	40	30	Luka Stražišar	30	452	1122	10
				Mai Rupnik	30	460	1079	8
				Brin Blazko	30	662	1643	7
				Aljaž Brodar	1	6	12	6
15	33	33	15	Luka Stražišar	15	166	611	10
				Mai Rupnik	15	168	383	8
				Brin Blazko	15	232	536	7
				Aljaž Brodar	1	2	4	6
16	33	37	300	Luka Stražišar	300	1395	3101	10
				Mai Rupnik	300	1531	3362	8
				Brin Blazko	300	2207	5002	7
				Aljaž Brodar	1	1	2	6
17	37	33	50	Luka Stražišar	50	777	2257	10
				Mai Rupnik	50	823	1841	8
				Brin Blazko	50	1085	2577	7
				Aljaž Brodar	1	6	10	6
18	37	33	50	Luka Stražišar	50	1174	2562	10
				Mai Rupnik	50	1212	2536	8
				Brin Blazko	50	1956	4665	7
				Aljaž Brodar	1	2	34	6
19	39	37	80	Mai Rupnik	80	1698	5713	10
				Luka Stražišar	80	3114	12356	8
				Brin Blazko	80	3992	11510	7
				Aljaž Brodar	1	2	14	6
20	39	39	20	Luka Stražišar	18	288	1472	10
				Mai Rupnik	18	350	1319	8
				Brin Blazko	18	562	2336	7
				Aljaž Brodar	1	28	111	6
21	91	91	20	Luka Stražišar	20	643	2750	10
				Mai Rupnik	20	699	1885	8
				Brin Blazko	20	761	2249	7
				Aljaž Brodar	1	15	43	6
22	94	88	1000	Mai Rupnik	1000	7647	18426	10
				Brin Blazko	1000	12169	28861	8
				Luka Stražišar	268	3165	17422	7
				Aljaž Brodar	1	2	5	6
23	94	94	100	Luka Stražišar	100	6687	21114	10
				Mai Rupnik	100	6799	15452	8
				Brin Blazko	100	9355	23641	7
				Aljaž Brodar	1	4	42	6
24	94	94	100	Mai Rupnik	100	7890	18689	10
				Brin Blazko	100	10958	29045	8
				Luka Stražišar	79	6440	17706	7
				Aljaž Brodar	1	9	90	6
25	97	97	20	Luka Stražišar	20	1050	3548	10
				Mai Rupnik	20	1102	2536	8
				Aljaž Brodar	1	12	54	7
26	93	89	1000	Mai Rupnik	1000	7217	16916	10
				Luka Stražišar	225	2073	14151	8
				Aljaž Brodar	2	2	6	7
27	85	97	100	Mai Rupnik	100	6059	13524	10
				Luka Stražišar	100	6199	17862	8
				Aljaž Brodar	1	12	24	7
28	89	93	100	Luka Stražišar	100	5183	11717	10
				Mai Rupnik	2	49	84	8
				Aljaž Brodar	1	27	42	7
29	97	91	300	Luka Stražišar	71	1946	19419	10
				Mai Rupnik	2	8	30	8
				Aljaž Brodar	1	1	27	7
30	93	95	25	Luka Stražišar	23	1892	17167	10
				Mai Rupnik	1	29	237	8
				Aljaž Brodar	0	0	1	7

Skupni seštevek

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

Ime in priimek	Rezultat
Luka Stražišar	288
Mai Rupnik	260
Aljaž Brodar	186
Brin Blazko	173

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