NézetNyomtat

Sakk
Címkék > Feladat

Sakk

Egy N $\times$ N-es sakktáblán bábukat helyeztünk el, amelyek helyükről nem mozdulnak el. Egyetlen futót mozgathatunk. Futó a sakktáblán mindig csak valamilyen átló irányában léphet, akárhányat, de bábut nem ugorhat át és nem is léphet más bábu helyére. Az átló irányú, akármilyen hosszú mozgatást tekintjük egy lépésnek.

Feladat

Készíts programot, amely egy adott sakktáblára és két pozícióra megadja, hogy

A. minimálisan hány lépés alatt juthat el a futó a kezdőpozícióról a végpozícióra!

B. minimálisan hány lépés alatt juthat el a futó a kezdőpozícióról a végpozícióra akkor, ha engedélyezzük, hogy az útjába eső bábukat leüsse (ekkor az adott lépés mindig a leütött bábu helyén ér véget)!

Bemenet

A SAKK.BE szöveges állomány első sorában a sakktábla mérete ($1 \le N \le 100$), valamint az elhelyezett bábuk száma ($1 \le K \lt 10000$) van, egyetlen szóközzel elválasztva. A második sorban 4 szám, a futó kezdő- és végpozíciója van ($1 \le KX,KY,VX,VY \le N$), egy-egy szóközzel elválasztva. A következő K sorban egy-egy bábu koordinátái vannak (1$\le$X,Y$\le$N). Biztosan tudjuk, hogy a futó kezdőpozícióján (KX,KY) nem áll más bábu.)

Kimenet

A SAKK.KI állományba pontosan 2 sort kell írni, a két részfeladat esetén a minimális lépésszámot! Ha valamelyik feladat nem oldható meg, akkor az adott sorba -1-et kell kiírni.

Példa

sakk.besakk.ki
8 5 6 3 2 7 5 2 3 3 3 6 6 7 8 5 3 2

Tesztadatok