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).

Í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!

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 oszlop2, ahol a sori és az oszlopi két szomszédos csomópont koordinátáit adja meg (1<=sori<=N, 1≤oszlopi≤M). Jelentése: a (sor1, oszlop1)-ből a (sor2, oszlop2)-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. 

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!

 

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

A feladat forrása: NTOITV 2013-2014, 2. forduló, 9-10. évfolyam

Algoritmusok: