Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az I/S. 64. feladat (2022. szeptember)

I/S. 64. Budapest belvárosában innovatív futárcéget alapítottak. A belvárost a cég egy \(\displaystyle N\) sorból és \(\displaystyle M\) oszlopból álló négyzetrácsként képzeli el. A négyzetrács \(\displaystyle n\)-edik sorában és \(\displaystyle m\)-edik oszlopában található egységnégyzetet \(\displaystyle T[n][m]\)-el jelöljük. A cég székhelye a \(\displaystyle T[a][b]\) mezőn helyezkedik el. A sorokat és oszlopokat 1-től indexeljük.

Egy nap rendelést kapnak a \(\displaystyle T[p][q]\) mezőről, ahova a futár szeretne a lehető leggyorsabban eljutni. Sajnos a futár még csak pályakezdő, ezért csak a sakkjáték futóra vonatkozó szabályai szerint tud mozogni Budapest belvárosában (csak átlósan mozoghat, de egy irányban tetszőlegesen sokat, ha a belvárosban marad).

Adjuk meg, hogy legkevesebb hány lépés alatt juthat el a futár a \(\displaystyle T[a][b]\) mezőről a \(\displaystyle T[p][q]\) mezőig, ha egy lépésben átlósan léphet tetszőlegesen sokat (a belvárosban maradva). Ha a futár sehogy sem tudja elérni a \(\displaystyle T[a][b]\) mezőt, akkor írjunk ki \(\displaystyle -1\)-et.

A bemenet első sorában az \(\displaystyle N\) és \(\displaystyle M\) számok szerepelnek szóközzel elválasztva. A második sorban az \(\displaystyle a\), \(\displaystyle b\), \(\displaystyle p\), \(\displaystyle q\) számok szerepelnek szóközzel elválasztva.

A kimenet egyetlen sorában egy szám szerepeljen, a minimális lépésszám (vagy \(\displaystyle - 1\), ha nem lehetséges elérni a célmezőt).

Példák:

Példa bemenetKimenet
5 4
2 2 4 4
1
12 4
1 1 11 3
4

Beküldendő egy tömörített s64.zip állományban a program forráskódja, valamint a program rövid dokumentációja, amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztői környezetben fordítható.

Korlátok: \(\displaystyle 2 \le N,M \le 10^{9}\), \(\displaystyle 1 \le a, p \le N\), \(\displaystyle 1 \le b,q \le M\). Időkorlát: 0,4 mp.

Értékelés: a pontok 50%-a kapható, ha a program az \(\displaystyle N,M \le 1000\) tesztesetekre helyes megoldást ad.

(10 pont)

A beküldési határidő 2022. október 17-én LEJÁRT.


Statisztika:

Az I/S. 64. feladat értékelése még nem fejeződött be.


A KöMaL 2022. szeptemberi informatika feladatai