Programozás‎ > ‎Feladatok‎ > ‎

Város

Egy modern nagyváros úthálózata egy négyzetráccsal írható le, ahol N jelöli a négyzetrács sorainak számát (azaz a kelet-nyugati irányú utak számát, az ilyen utakat alulról felfelé sorszámozzuk), M pedig az oszlopokét (azaz az észak-déli utakét, az ilyen utakat balról jobbra
sorszámozzuk). El szeretnénk jutni a város egyik kereszteződéséből egy másik kereszteződésbe. Az egyes kereszteződések (csomópontok) előtt a haladási irányt befolyásoló jelzőtáblák lehetnek, melyeket a következő kódokkal látunk el:
  • balra fordulni tilos          BT
  • jobbra fordulni tilos        JT
  • balra haladni kötelező    BK
  • jobbra haladni kötelező  JK
Visszafordulni semelyik csomópontban sem lehet, azaz ha nincs jelzőtábla, akkor is csak maximum háromfelé haladhatunk. Útközben a várost nem hagyhatjuk el (bár erről szóló jelzőtáblák nincsenek). Az indulási helyről bármerre indulhatunk, azt nem befolyásolja tábla. 

Feladat

Írjunk programot, ami a táblák figyelembevételével megadja a legrövidebb útvonalat, amelyeken áthaladva eljuthatunk az indulási helyről a célba!

Bemenet

A varos.be állomány első sorában a sorok és oszlopok száma (1 <= N, M <= 100), valamint a táblák száma (1 <= T <= 10 000) van egy-egy szóközzel elválasztva. A következő T sorban soronként egy-egy tábla leírása található. A táblaleírás formája: irány sor oszlop kód, ahol a sor és az oszlop a csomópont koordinátáit adja meg (1 <= sor <= N, 1 <= oszlop <= M), az irány pedig a csomópontba beérkező útszakasz irányát (E, K, D, N), azaz a beérkező út északi, keleti, déli vagy nyugati irányban halad-e. Az utolsó sorban a két kereszteződés sor és oszlopindexe van, egy-egy szóközzel elválasztva, az első az induló hely, a második a cél. 

Kimenet

A varos.ki állomány első sorába a két pont közötti legrövidebb út hosszát kell írni! A második sorba a legrövidebb út leírását kell írni, ahol minden lépést a haladás iránya, azaz az E, K, D vagy N betű azonosít. Feltehető, hogy ilyen út mindig van! 

Példa

Bemenet  Kimenet
4 3 5
E 2 1 JK
K 2 2 JK
E 2 2 BT
E 4 2 BT
E 4 2 JT
1 1 4 1
5
KEENE


E 2 1 JK magyarázata: Ha északi irányba haladva a (2,1) pontba érünk, akkor ott kötelező jobbra fordulni, azaz innen csak keleti irányba a (2,2) pontba mehetünk.


Tesztadatok

Címkék

A feladat forrása: NTOITV 2013-2014, 2. forduló, 11-13. évfolyam
Algoritmusok: