A2 - Parkovanie (ťažké)

Úloha

Vytvorte program, ktorý nájde najbližšie parkovacie miesto pre vozidlo a vypíše, koľko krokov treba vykonať, aby tam šofér vedel zaparkovať.

Vstup

Prvý riadok obsahuje rozmery mapy parkoviska R (1 ≤ R ≤ 150) a S (1 ≤ S ≤ 150).

Nasleduje mapa parkoviska pozostávajúca z R riadkov po S stĺpcov. Každému políčku zodpovedá práve 1 písmeno. Význam písmen je nasledovný:

• x - prekážka,
• . - voľné miesto,
• w, s, a, d - pozícia vjazdu vozidla na parkovisko v smere hore, dole, vľavo, vpravo,
• ^, v, <, > - voľné parkovacie miesto pre vozidlo v smere hore, dole, vľavo, vpravo.

Vozidlo je reprezentované 2 políčkami (písmeno o sa na mape nenachádza, slúži ako vizualizácia zadnej časti vozidla) a dokáže:

- pohnúť sa dopredu (1 krok)

.....    .....
.....    ..w..
..w.. -> ..o..
..o..    .....
.....    .....

cúvať dozadu (1 krok)

.....    .....
.....    .....
..w.. -> .....
..o..    ..w..
.....    ..o..

- pohnúť sa dopredu a otáčať doľava, ak pred ním nie je prekážka (3 kroky)

.....    .....
.....    ao...
xxw.. -> xx...
.xo..    .x...
.....    .....

- pohnúť sa dopredu a otáčať doprava, ak pred ním nie je prekážka (3 kroky)

..xxx    ..xxx
.....    ...od
..w.. -> .....
..o..    .....
.....    .....

- cúvanie s otáčaním nie je povolené, lebo nie každý šofér je si istý otáčať počas cúvania.

Môžete predpokladať, že:

• mapa parkoviska je ohraničená prekážkami,
• na mape je iba jedna pozícia vjazdu vozidla,
• na mape je aspoň jedna pozícia na parkovanie určená pre vozidlo,
• políčko za vozidlom nie je prekážka,
• políčko za parkovacím miestom tiež nie je prekážka.

Výstup

Výstupom programu je najmenší počet krokov potrebných na zaparkovanie vozidla. Ak nie je možné zaparkovať vráťte -1.

Príklad

Vstup:

6 7
xxxxxxx
x.xxxxx
xsx.x^x
x.xvx.x
x.....x
xxxxxxx

Výstup:

8

Vstup:

7 10
xxxxxxxxxx
xxxxx.xxxx
xxxxxsxxxx
xxxxx^xxxx
xxxxx.xxxx
x........x
xxxxxxxxxx

Výstup:

  
11