Synchronizace robotů

Za námět úlohy vděčíme Jonathanu Weltonovi a jeho úloze Thunderball na stránkách http://www.mathpuzzle.com/26Mar03.html.

Obdélníková oblast je rozdělena na čtvercová pole a má M řádků a N sloupců. Na některých polích stojí roboti. Robotů je celkem K (1 ≤K ≤ M×N) a na každém poli stojí nejvýše jeden. Roboti se pohybují v krocích a během svého pohybu každý robot označí každé pole, na které dorazí. V každém kroku se každý robot může posunout na pole bezprostředně sousední vlevo, vpravo, nahoře nebo dole a přitom toto pole nesmí být označené. Na začátku jsou označená pouze pole, na kterých jednotliví roboti stojí.

Roboti vykonávají jednotlivé kroky vždy současně na příkaz dispečera. Dispečer má k dispozici čtyři příkazy označené zkratkami L, H, P, D podle směru pohybu (doLeva, naHoru, doPrava, Dolu). Když dispečer vydá příkaz, každý z robotů se pokusí posunout o jedno pole ve směru daném v příkazu. Pokud je sousední pole v daném směru označené, to jest buď na něm stojí jiný robot nebo na něm kterýkoli z robotů již dříve stál, robot se neposune a zůstane stát. Robot se nemůže přesunout mimo danou obdélníkovou oblast, pokud stojí těsně u hranice oblasti a má se podle příkazu posunout v takovém směru, že by hranici překročil, také zůstane stát.

V oblasti je dále vyznačeno K tzv. cílových polí, na něž se mají roboti postupně přesunout tak, že po určitém počtu příkazů vydaných dispečerem bude každý robot stát na jednom cílovém poli. Nezáleží na tom, který robot bude stát na kterém cílovém poli.

Úloha
Na začátku je dán seznam polí, na kterých jednotliví roboti stojí před zahájením přesunu, a seznam cílových polí. Máme určit všechny takové co nejkratší posloupnosti příkazů dispečera, že po provedení kterékoli z nich budou všichni roboti stát na cílových polích.

Poznámka: Když robot během svých přesunů dorazí na některé pole, ať už cílové nebo ne, a dispečer vydá další příkaz a robot může toto pole opustit, pak také robot toto pole opustí. Niceméně tím, že robot toto pole při svém příchodu označil, zároveň znemožnil další návrat kteréhokoli robota na toto pole. Proto, pokud robot opustí cílové pole, znemožní tak řešení úlohy.

Obr. 1. Příklad. Roboti označení A a B stojí na polích se souřadnicemi (1, 1) a (2, 4), mají se přesunout na cílová pole se souřadnicemi (2, 1) a (1, 4), cílová pole jsou podbarvena. Existují dvě nejkratší posloupnosti příkazů délky 7, pomocí nichž se přesun provede. Prostřední diagram znázorňuje přesun podle posloupnosti LDLHHPP, levý diagram znázorňuje přesun podle posloupnosti PHPDDLL.

Vstup

Na vstupu jsou tři textové řádky. První řádek obsahuje čísla M, N, K v tomto pořadí oddělená mezerou. Druhý řádek obsahuje K celočíselných dvojic, každá dvojice obsahuje nejprve řádkovou a potom sloupcovou souřadnici jednoho robota. Třetí řádek obsahuje opět K celočíselných dvojic, každá dvojice obsahuje nejprve řádkovou a potom sloupcovou souřadnici jednoho cílového pole. Všechny hodnoty na řádku jsou odděleny mezerou, řádkové i sloupcové souřadnice se počítají od 0. Žádný robot nestojí na žádném z cílových polí.
Počet polí v oblasti nepřesáhne 50.

Výstup

Pokud neexistuje žádná posloupnost příkazů, pomocí níž se roboti mohou přesunout na cílová pole podle pravidel úlohy, výstup obsahuje jediný textový řádek s číslem 0.
Jinak výstup obsahuje jeden nebo více textových řádků, z nichž každý obsahuje jednu posloupnost příkazů, pomocí níž se roboti mohou přesunout na cílová pole. Posloupnosti na výstupu jsou navzájem různé, nejkratší možné a všechny možné. Posloupnosti na výstupu jsou seřazeny v rostoucím lexikografickém pořadí, přičemž pro jednotlivé příkazy formálně platí L < H < P < D.
Počet posloupností na výstupu nepřesáhne 1000.

Příklad 1

Vstup:

4 6 2
1 1 2 4 
2 1 1 4 

Výstup:

LDLHHPP
PHPDDLL

Vstup a výstup popisuje situaci znázorněnou na Obr. 1. výše.

Příklad 2

Vstup:

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

Výstup:

LPHD
LPDH
HDLP
HDPL
PLHD
PLDH
DHLP
DHPL

Obr. 2. Obrázek znázorňuje výchozí postavení robotů (A, B, C, D) a podbarvená cílová pole odpovídající datům příkladu 2. Rekonstrukce posunů robotů podle jednotlivých posloupností příkazů je jednoduché cvičení, ponecháváme je na řešiteli.

Příklad 3

Vstup:

3 7 3
1 3 2 6 2 1 
1 6 1 1 0 0 

Výstup:

LHLHPPD

Obr. 3. Obrázek znázorňuje posun robotů odpovídající datům příkladu 3.

Veřejná data

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