 |
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 bemenet | Kimenet |
|---|---|
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:
7 dolgozat érkezett. 10 pontot kapott: Mészáros Anna Veronika, Zádor-Nagy Zsombor. 8 pontot kapott: 1 versenyző. 6 pontot kapott: 1 versenyző. 5 pontot kapott: 1 versenyző. 4 pontot kapott: 1 versenyző. 2 pontot kapott: 1 versenyző.
A KöMaL 2022. szeptemberi informatika feladatai