Hlavolam

Zadání: http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=hlavolam

Mějme hlavolam, který představuje dvojrozměrné pole s rozměry M×N. Každé políčko hlavolamu obsahuje přirozené číslo v rozsahu od 1 do M·N. Každé číslo od 1 do M·N je v hlavolamu zastoupeno právě jediným políčkem. Nad hlavolamem jsou povoleny provádět pouze následující čtyři operace:

levá rotace řádku, pravá rotace řádku, levá rotace sloupce, pravá rotace sloupce.

Rotace je definovaná následovně:

Nechť a₀ až a_k-1 jsou všechna políčka nějakého vybraného řádku nebo sloupce, který chceme rotovat. Pravá rotace permutuje políčka podle jejich indexů permutací pR, kde pR[i]=(i+1) mod k. Levá rotace permutuje políčka podle jejich indexů permutací pL, kde pL[i]=(i+k-1) mod k.

Úkolem pro Vás je zjistit, jaké je potřeba nejmenší množství operací k složení hlavolamu ze zadaného startovního stavu do zadaného cílového stavu.

Na prvním řádku budou dvě čísla M a N oddělená mezerou udávající rozměry hlavolamu.

Na dalších řádcích budou za sebou následovat dva hlavolamy. První bude popisovat startovní hlavolam a druhý bude popisovat cílový hlavolam.

Každý hlavolam bude představovat M řádků, kde na každém řádku bude N přirozených čísel oddělených mezerou.

Předpokládejte, že vstupní formát je vždy korektní a maximální možná velikost hlavolamu je vždy menší nebo rovna 20. Velikostí hlavolamu myslíme počet políček hlavolamu tj. součin M·N.

Výstupem bude vždy jediný řádek s celým číslem udávajícím minimálním počet operací potřebných k složení hlavolamu. Pokud složení hlavolamu nebude možné, bude výsledné celé číslo -1.

Vstup:

2 4
1 2 3 4
5 6 7 8 
2 5 6 1
8 3 4 7

Výstup:

4

Startovní hlavolam:

1 2 3 4
5 6 7 8 

Levá rotace prvního řádku:

2 3 4 1
5 6 7 8 

Pravá rotace druhého řádku:

2 3 4 1
8 5 6 7  

Levá rotace druhého sloupce:

2 5 4 1
8 3 6 7  

Pravá rotace třetího sloupce:

2 5 6 1
8 3 4 7