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ésekből kivezető néhány út elejére behajtani tilos táblákat helyeztünk el, arra értelemszerűen nem lehet haladni.
Útközben a várost nem hagyhatjuk el (bár erről szóló jelzőtáblák nincsenek).
Feladat
Írjunk programot, amely 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 utcak.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: sor1 oszlop1 sor2 osz
lop2
, ahol a sor
i
és az oszlop
i
két szomszédos csomópont koordinátáit adja meg (1<=sor
i
<=N, 1≤oszlop
i
≤M)
. Jelentése: a (sor
1
, oszlop
1
)
-ből a (sor
2
, oszlop
2
)
-be vezető útra behajtani tilos tábla van. 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 utcak.ki
állomány első sorába a két pont közötti legrövidebb út hosszát kell írni! A második sorba egy 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 4
1 1 2 1
2 2 2 1
4 2 4 1
4 2 4 3
1 1 4 1
1 1 2 1
|
5
KEENE
|
Tesztadatok
Címkék
A feladat forrása: NTOITV 2013-2014, 2. forduló, 9-10. évfolyam
Algoritmusok: