Cesta věže

Popis úlohy

Na šachovnici o rozměrech 8 × 8 se nachází věž (v), cíl (c), případně některá pole označená jako překážky (x). Ostatní pole jsou prázdná (.).

Věž se pohybuje stejně jako věž v šachu — může se přesunout o libovolný počet polí vodorovně nebo svisle, ale nemůže překročit ani přeskočit překážku. Každý takový tah (bez ohledu na počet polí, o která se věž přesune) se počítá jako jeden krok.

Vaším úkolem je najít minimální počet kroků, které věž potřebuje k dosažení cílového pole. Pokud cíle dosáhnout nelze, vypište -1.

Vstup

Vstup tvoří právě 8 řádků, každý obsahuje právě 8 znaků. Každý znak je jeden z následujících:

Vstup vždy obsahuje právě jednu věž (v) a právě jeden cíl (c).

Výstup

Vypište jediné celé číslo — minimální počet kroků potřebných k přesunu věže na cílové pole. Pokud cílového pole nelze dosáhnout, vypište -1.

Příklad vstupu

........
...x....
.v..x...
........
..x..x..
........
.....c..
........

Příklad výstupu

3

Vysvětlení příkladu

Věž začíná na pozici (řádek 2, sloupec 1). Jeden z optimálních postupů:

1. Věž se přesune dolů na řádek 5, sloupec 1.

2. Věž se přesune vpravo na řádek 5, sloupec 5.

3. Věž se přesune dolů na řádek 6, sloupec 5 — cíl.

Celkem 3 kroky.

Poznámky

• Překážka blokuje pohyb věže — věž se nesmí přesunout přes pole označené x ani na něj.

• Věž se může přesunout o jedno nebo více volných polí v rámci jednoho kroku, pokud jsou všechna mezipolí volná.