Hatszög
Egy szabályos hatszög alakú térképet szabályos hatszögekre bontottunk úgy, hogy minden oldalán
N darab kisebb hatszög lett. A szemben levő csúcsokat összekötő átlókra az ábra szimmetrikus, így a hatszögeket 3 index-szel azonosíthatjuk (mindegyik az egyik tengely mentén állandó). Az
i index a vízszintes tengely mentén állandó, felfelé csökken, lefelé nő. A
j index a jobbra lefelé haladó tengely mentén állandó, ettől balra csökken, jobbra pedig nő. A
k index pedig a balra lefele haladó tengely mentén állandó, ettől balra növekszik, jobbra pedig csökken.
Így az
(i,j,k) indexű elem szomszédai indexei az ábra szerint alakulnak. Legyen a középső kis hatszög indexe a
(0,0,0)! Minden egyes pontnak ismerjük a tengerszint feletti magasságát.
Feladat
Készíts programot, amely a (p,q,r) indexű pontból meghatározza a legrövidebb olyan ún. vízszintes út hosszát az (x,y,z) pontba, melynek során a tengerszint feletti magasság nem változik!
Bemenet
A HATSZOG.BE állomány első sorában a nagy hatszög mérete $(1\le N \le 80)$ van. A következő $2\cdot N-1$ sorban annyi tengerszint feletti magasság van (0<magasság $\le 1000)$, amennyi a térkép egy-egy sorához szükséges. Az utolsó sorban a kezdő- (p,q,r) és a végpozíció (x,y,z) indexei találhatók, egy-egy szóközzel elválasztva.
Kimenet
A HATSZOG.KI egyetlen sorába a legrövidebb (p,q,r)-ből (x,y,z)-be vezető vízszintes út hosszát kell írni. Ha ilyen út nincs, akkor a kiírt szám legyen -1!
Példa
| hatszog.be | hatszog.ki |
| 3
5 6 7
1 1 1 8
1 2 3 2 1
1 1 1 1
1 1 1
-1 -1 2 1 0 -1 |
4 |
Tesztadatok
