Egy térképet egy NxM-es mátrixban ábrázolunk. A városokat a mátrixban a 2-es számjegy, az utakat pedig az 1-es számjegy jelzi. A többi ponthoz tartozó érték 0. Az utak minden pontból a 4 szomszédos pont irányában folytatódhatnak, azaz átlósan lépni nem lehet. Egy város több 2-es értékű pontból is állhat, de két város sehol sem érintkezhet egymással, azaz nincs két szomszédos pontjuk.
Feladat:
Készíts programot, amely két város esetén megadja a városok területét (hány 2-es értékű pontból áll), valamint két a közöttük vezető legrövidebb út hosszát az alábbi háromféle módon:
ˇ a legrövidebb az az út, ami a legkevesebb várost érinti a kiindulásin kívül;
ˇ a legrövidebb út az az út, ami legkevesebb, egyik városhoz sem tartozó (1-es értékű) közbülső ponton halad át;
ˇ a legrövidebb út az az út, amin a leggyorsabban el lehet érni a másik városba, feltételezve, hogy városban feleakkora a sebesség, mint a városok közötti utakon, azaz az 1-essel jelölt pontot 1, a 2-essel jelölt pontot pedig 2 időegység alatt lehet elhagyni.
Bemenet:
A TERKEP.BE állomány első sorában N és M értéke van (1<=N, M<=100), egy-egy szóközzel elválasztva. A további N sor mindegyike pontosan M számjegyet tartalmaz (csak 0, 1 vagy 2 lehet) szóközök nélkül, a térkép egyes sorai leírását. Az állomány utolsó sora két város indexeit ((X,Y) és (U,V)), azaz négy számot tartalmaz (1<=X, U<=M, 1<=Y, V<=N), s a feladat az (X,Y)-ból (U,V)-be vezető legrövidebb út megtalálása. Az első sor első (bal oldali) elemének koordinátái (1,1), az N. sor M. elemének pedig (N,M).
Kimenet:
A TERKEP.KI állományba négy sort kell írni. Az első sorban (X,Y), illetve az (U,V) pontot tartalmazó város területét kell írni, egy szóközzel elválasztva. A következő három sorban egyetlen szám szerepeljen: a feladatban szereplő három megfogalmazásbeli legrövidebb út hossza. Ha nincs út a két város között, akkor -1-et kell írni mindhárom sorba.
Példa:
|
TERKEP.BE |
TERKEP.KI |
|
9 10
|
3 5
|
(Nemes Tihamér 2000. döntő)