A - Kravička

Niektorí cvičiaci PAZka si veľmi obľúbili hru Kravičky (IQ Marathon). Je to jednoduchá hra. Hrá sa v mriežkovej ploche, v ktorej sa nachádza kravička. Kravička sa vždy hýbe tým smerom, ktorým je natočená, až dokiaľ nenarazí na prekážku. Vtedy zastane. Avšak ak kravička narazí na políčko s navigačnou šípkou, zmení svoj smer pohybu v smere tejto šípky (otočí sa vľavo, vpravo alebo čelom vzad). Úlohou hráča je umiestniť do hracej plochy zadané navigačné šípky tak, aby sa kravička zo svojej východiskovej pozície dostala do zadanej cieľovej pozície. Na štartovaciu pozíciu kravičky nie je možné umiestniť navigačnú šípku (na začiatku je toto políčko obsadené kravičkou).

Pre väčšinu hráčov tejto hry je cieľom stať expertom - dostať sa do najvyššieho levelu. No sú aj takí, čo si pri tejto hre kladú algoritmické otázky. Napríklad, aký je minimálny počet šípok, ktoré musíme použiť pre vyriešenie zadaného levelu (rozmer mriežky, umiestnenie prekážok, počiatočná pozícia a smer kravičky, cieľová pozícia)?

Úloha

Vytvorte program, ktorý načíta popis levelu a vypočíta minimálny počet šípiek na zmenu smeru kravičky, ktoré sú potrebné na to, aby sa kravička dostala do cieľovej pozície.

Vstup

Prvý riadok vstupu obsahuje dve medzerou oddelené čísla m a n (5 ≤ m, n ≤ 90), kde m je počet riadkov (výška) hracej plochy (mriežky) a n je počet stĺpcov (šírka) hracej plochy. V nasledujúcich m riadkoch nasleduje opis riadkov hracej mriežky v danom levele. Každému políčku zodpovedá jedno písmeno:

• medzera - prázdne políčko,
• X - políčko s prekážkou,
• C - cieľové políčko,
• H - štartovacia pozícia kravičky, ktorá je natočena smerom nahor,
• P - štartovacia pozícia kravičky, ktorá je natočena smerom vpravo,
• D - štartovacia pozícia kravičky, ktorá je natočena smerom nadol,
• L - štartovacia pozícia kravičky, ktorá je natočena smerom vľavo.

Možete predpokladať, že celá hracia plocha je olemovaná políčkami s prekážkami a nachádza sa na nej práve jedno štartovacie a cieľové políčko.

Výstup

Výstupom je minimálny počet šípiek, ktoré je nutné umiestniť v ploche, aby bolo možné kravičku odnavigovať do cieľovej pozície, resp. -1 ak sa kravička nedá dostať do cieľovej pozície. Výstup ukončite znakom konca riadku.

Príklad

Vstup:

20 30
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X X                  X
X    X               X  XX   X
X                            X
X               X            X
X                    X       X
X        XX          X       X
X           X    XXXXXXXXXXXXX
X    H                  X   XX
X       X               X    X
X  XXXXXX         XX         X
X X               X       X  X
X  X XX   X             X    X
X     X              XXXX    X
X     X          X           X
X     X        XXXXXXXXXX  X X
X   X XX                X   XX
X     X         X       X    X
X              X     C       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Výstup:

4