Prihlásenie Registrácia  

A2 - pArkovanie 2

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Určite ste sa stretli s problémom hľdania parkovacieho miesta na platených parkoviskách, najmä ak je málo parkovacích miest. Spoločnosť PArkovanie Limuzín Motoriek Aut sa rozhodla, že vytvori parkovací systém, ktorý odnaviguje šoféra na najbližšie parkovacie miesto určené priamo pre neho.

Ú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