Informatika gyűjtemény

Egy szinttel feljebb Hatszög

2004050607080910

NézetNyomtat

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