Zadání úlohy z A4B33ALG

Jezdci a věže

Na šachovnici o rozměrech W×H je v počátečním postavení rozestaveno W×H−1 šachových figur tak, že na každém poli kromě jediného stojí jedna figura. Uvedené volné pole může být kdekoli na šachovnici, figurou může být pouze jezdec nebo věž. Na barvě figur nezáleží.
K dipozici máme také koncové postavení figur, které obsahuje stejný počet jezdců a věží jako obsahuje počáteční rozestaveni, ale tyto figury mohou stát na jiných polích, také volné pole může být jinde. Máme za úkol pomocí jednotlivých kroků přejít z počátečního postavení do koncového.

V jednom kroku lze přemístit jen jednu figuru, a to v souladu s šachovými pravidly pohybu této figury. Pokud stojí některá z věží na poli sousedícím s volným polem, může být v jednom kroku tato věž na volné pole přesunuta. Pokud stojí některý z jezdců tak, že se jedním skokem může přesunout na volné pole, lze tento skok učinit v jednom kroku.

Jednotlivé figury stejného druhu považujeme za navzájem nerozlišitelné. To znamená, že záleží pouze na tom, aby všechny věže, které jsou na šachovnici v počátečním postavení, obsadily právě všechna pole obsazená věžemi v koncovém postavení, přičemž nezáleží na tom, kde která jednotlivá věž bude za těchto okolností nakonec stát. Stejné pravidlo nerozlišitelnosti platí pro jezdce.

Obr. 1.
Příklad. Schéma a) předtavuje počáteční konfiguraci, schéma i) koncovou konfiguraci, navzájem se liší pouze pořadím figur v řádku 0. Přechod lze provést v 8 krocích, stav po jednotlivých krocích je naznačen na schématech b) - i).

Úloha
Máme zjistit, jaký je nejmenší nutný počet kroků k tomu aby se dalo přejít z počátečního postavení do koncového při zachování uvedených pravidel, a vypsat jednu z možných posloupností kroků, jimiž se přechod s nejmenším možným počtem kroků uskuteční.

Vstup

Na vstupu je několik textových řádků. První řádek obsahuje dvě celá kladná čísla navzájem oddělená mezerou W, H. Tato čísla představují v tomto pořadí šířku a výšku naší šachovnice. Každý z dalších H řádků obsahuje řetězec délky W sestavený ze znaků množiny {'1', '0', '.'}. Znak '1' představuje jezdce, znak '0' představuje věž a znak '.' (tečka) představuje volné pole. Všech H řádků s řetězci představuje dohromady šachovnici s H řádky a W sloupci. Sloupce šachovnice jsou indexovány zleva doprava 0, 1, ..., W−1, řádky šachovnice jsou indexovány shora dolů 0, 1, ..., H−1. První znak prvního řetězce tedy odpovídá poli šachovnice s řádkovým i sloupcovým indexem 0, poslední znak posledního řetězce odpovídá odpovídá poli šachovnice s řádkovým indexem H−1 a sloupcovým indexem W−1. Uvedených H řádků určuje počáteční rozestavení figur na šachovnici. Za nimi následuje nejprve řádek s řetězcem sestávajícím výhradně z nenulového počtu znaků minus (slouží jako vizuální oddělovač) a potom dalších H řádků určujících koncové rozestavení figur zapsané ve stejném formátu. Počet věží v počátečním postavení se shoduje s počtem věží v koncovém postavení, totéž platí pro jezdce.

Platí, že šachovnice obsahuje nejvýše 50 polí a přechod z počátečního do koncového postavení je vždy možný.

Výstup

Výstup obsahuje dva textové řádky. Na prvním řádku je zapsán minimální možný počet kroků, jimiž lze z počátečního postavení přejít do koncového. Druhý řádek tuto posloupnost kroků explicitně popisuje. Každý krok je popsán dvěma čísly r a s , která představují řádkový a sloupcový index prázdného pole po provedení tohoto kroku, tj. určují pole, které v tomto kroku opustila jedna z figur. Na výstupu je každý z indexů r a s zapsán vždy pomocí dvou číslic s případnou úvodní nulou, indexy r a s jsou zapsány za sebou a odděleny dvojtečkou, jednotlivé dvojice indexů jsou navzájem odděleny jednou mezerou. Pokud je nejkratších možných posloupností kroků více, vystoupí pouze ta z nich, jejíž zápis na výstupu, chápaný jako jeden řetězec, je nejmenší možný v lexikografickém uspořádání.

Příklad 1

Vstup:

Výstup:

8
01:02 02:02 01:00 00:02 00:01 02:02 01:02 00:00

Příklad 1 je znázorněn na obrázku v textu.

Příklad 2

Vstup:

Výstup:

16
00:01 00:02 00:03 01:05 01:06 02:06 03:06 02:04 00:03 00:04 00:05 01:05 03:06 04:06 05:06 06:06

Příklad 3

Vstup:

23 2
11100000000000000000000
0000000000000000000000.
---
00000000000000000000111
0000000000000000000000.

Výstup:

146
01:21 01:20 01:19 01:18 01:17 01:16 01:15 01:14 01:13 01:12 01:11 01:10 01:09 01:08 01:07 01:06 01:05 01:04 00:02 00:03 00:04 00:05 00:06 01:04 01:03 00:01 00:02 00:03 00:04 00:05 01:03 01:02 00:00 00:01 00:02 00:03 00:04 01:02 01:03 01:04 01:05 01:06 01:07 01:08 00:06 00:07 00:08 00:09 00:10 01:08 01:07 00:05 00:06 00:07 00:08 00:09 01:07 01:06 00:04 00:05 00:06 00:07 00:08 01:06 01:07 01:08 01:09 01:10 01:11 01:12 00:10 00:11 00:12 00:13 00:14 01:12 01:11 00:09 00:10 00:11 00:12 00:13 01:11 01:10 00:08 00:09 00:10 00:11 00:12 01:10 01:11 01:12 01:13 01:14 01:15 01:16 00:14 00:15 00:16 00:17 00:18 01:16 01:15 00:13 00:14 00:15 00:16 00:17 01:15 01:14 00:12 00:13 00:14 00:15 00:16 01:14 01:15 01:16 01:17 01:18 01:19 01:20 00:18 00:19 00:20 00:21 00:22 01:20 01:19 00:17 00:18 00:19 00:20 00:21 01:19 01:18 00:16 00:17 00:18 00:19 00:20 01:18 01:19 01:20 01:21 01:22

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