Kontejner

Schéma 1.

Na schématu je naznačen půdorys obdélníkového skladiště, v němž je několik kontejnerů. Jeden (oranžový, s číslem 0) kontejner je význačný, ten se má přemístit ze své pozice na novou pozici. Je to jediný kontejner, se kterým lze pohybovat, s žádným dalším se pohybovat nesmí.

Na levé straně schématu je výchozí konfigurace kontejnerů, na pravé straně je cílová konfigurace. Ve výchozí konfiguraci je přerušovanou čárou naznačena žádoucí cílová pozice oranžového kontejneru.

Podlaha skladiště je rozdělena čtvercovou sítí na jednotlivé dlaždice. Kontejnery stojí tak, že všechny hrany jejich půdorysů leží na přímkách sítě. To platí i pro přesouvaný kontejner na začátku a na konci každého jeho kroku.

Přesun probíhá v krocích tak, že se v jednom kroku kontejner posune o jednu dlaždici v některém ze čtyř směrů rovnoběžných s osami x, y rovněž na schématu vyznačenými. Při přesunu nesmí kontejner prorazit obvodovou zeď skladiště, může se jí ale dotýkat nebo sunout se podle ní. Také nesmí žádný jiný kontejner odtlačovat z jeho místa kamkoli jinam, i kdyby to byl kontejner znatelně menší. Může se ale těsně podél jiného kontejneru sunout podobně jako podle obvodové stěny skladiště nebo být k němu těsně přiražen. Při přesunu se kontejner nemůže otáčet nebo natáčet, jeho stěny musí stále zůstávat rovnoběžné se stěnami skladiště.

Doba, za kterou při přesunu vykoná kontejner jeden krok, není vždy stejná. Rozlišíme pomalejší a rychlejší kroky. Pokud se před provedením kroku nebo po jeho dokončení nebo během jeho provádění přesouvaný kontejner dotýká stěny skladiště nebo jiného kontejneru svou stěnou nebo rohem, je nutno dávat při přesunu větší pozor, proto krok trvá déle a je pomalejší. Naopak, když se ani před zahájením kroku ani během jeho provádění ani po jeho ukončení nedotkne přesouvaný kontejner jiného kontejneru ani stěny skladiště, trvá krok kratší dobu a je rychlejší. Kupříkladu na druhém schématu níže se přesouvaný kontejner dotýká kontejneru 1 rohem po provedení posledního kroku, takže poslední krok v tomto případě bude vždy krok pomalejší, ať už trasa přesunu předtím povede kudykoli.

Schéma 2.

Poloha každého kontejneru je zadána dvěma dvojicemi souřadnic. První dvojice představuje souřadnice té dlaždice, která ze všech dlaždic kontejnerem pokrytých je nejblíže počátku souřadnic, a druhá dvojice představuje souřadnice té dlaždice, která je ze všech dlaždic kontejnerem pokrytých nejdále od počátku souřadnic. Pokud kontejner pokrývá jedinou dlaždici, první a druhá dvojice souřadnic jsou shodné. Na prvním schématu je poloha kontejneru 0 dána souřadnicemi [0 1], [2 2], poloha kontejneru 1 souřadnicemi [4 2], [5 3] a poloha kontejneru 2 souřadnicemi [1 4], [1 5].

Cílová požadovaná poloha je dána pouze první ze dvojice souřadnic, druhou dvojici lze ze znalosti rozměrů přesouvaného kontejneru snadno dopočíst. Na prvním schématu je cílová poloha zadána dvojicí [3 4]. Všechny souřadnice dlaždic ve skladišti jsou nezáporné, skladiště obsahuje dlaždici se souřadnicemi [0 0].

Vstup

První řádek vstupu obsahuje dvě celá kladná čísla N, M představující rozměr skladiště podél osy x a rozměr skladiště podél osy y. Rozměr je vyjádřen v počtu dlaždic, kout skladiště nejvzdálenější od počátku má souřadnice [N−1 M−1]. Na dalším řádku je uvedena celočíselná doba trvání rychlého a pomalého kroku, v tomto pořadí. Další řádek obsahuje jediné celé číslo K udávající počet kontejnerů ve skladišti. Na dalších K řádcích jsou uvedeny souřadnice kontejnerů, každý řádek specifikuje jeden kontejner a obsahuje jeho souřadnice v pořadí x1, y1, x2, y2, kde [ x1 y1] a [x2 y2] specifikují souřadnice rohů kontejneru tak, jak je uvedeno výše v zadání. Souřadnice přesouvaného kontejneru jsou uvedeny na prvním místě před souřadnicemi všech ostatních kontejnerů. Poslední řádek vstupu obsahuje první dvojici souřadnic cílové polohy přesouvaného kontejneru.
Žádná stěna skladiště není delší než 100 dlaždic, ve skladišti je vždy alespoň jeden kontejner, zadané souřadnice kontejnerů vzájemně ani se stěnami skladiště nekolidují, nevytvářejí fyzicky nemožné kombinace.

Výstup

Na výstupu je jediný řádek s číslem udávajícím nejkratší možný čas přesunu kontejneru 0 z počáteční na koncovou pozici. Pokud kontejner na koncovou pozici přesunout nelze, je na řádku uvedeno číslo −1.

Příklad 1

Z prvního obrázku. Vstup:

9 7
1 1
3
0 1 2 2
4 2 5 3
1 4 1 5
3 4

Výstup:

14

Optimal route: SEEEEEENNNNWWW {N,S,W,E} - movement direction abbreviation(North, South, West, East)

Příklad 2

Z druhého obrázku. Vstup:

9 6 
1 8 
4
1 2 2 2 
3 2 3 2 
8 2 8 4 
1 0 1 0 
4 1 

Výstup:

31

Optimal route: NNEEEESSSW

Příklad 3

Vstup:

6 6 
1 2 
3
0 0 2 2 
4 1 4 1 
1 4 1 4 
3 3

Výstup:

-1

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data