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:
2004-2016 BDG algoritmus szakkör