Fejtörők megoldásai

20. Kapd el a bolhát!

Tegyük fel, hogy az n. időpillanatban vagyunk és tudjuk, hogy eredetileg hová pottyan a mi kis bolhánk: (i,j). Ezesetben 4 lépésben megtalálhatjuk, ugyanis akkor
- az n. időpillanatban feltételezve, hogy a bolha É-nak indult az (i,j+n) pontban kell lennie
- az n+1. időpillanatban feltételezve, hogy a bolha D-nek indult az (i,j-n-1) pontban kell lennie
- az n+2. időpillanatban feltételezve, hogy a bolha K-nek indult az (i+n+2,j) pontban kell lennie
- az n+3. időpillanatban feltételezve, hogy a bolha Ny-nak indult az (i-n-3,j) pontban kell lennie
Így a 4 tippből valamelyikkel elkapjuk a bolhát.

Ha ezt tudjuk, akkor már csak szisztematikusan be kell járnunk a koordinátarendszert, hiszen akkor előbb-utóbb a tényleges kiindulási pontra lépünk és akkor 4 lépésen belül elkapjuk a bolhát (a 0. lépésben nyilván nem kell a négy irányt külön vizsgálni). A szisztematikus bejárásra egy módszer a csigavonal, amit mondjuk indíthatunk az origóból.

Ennek megfelelően az első néhány tipp:
(0,0),
(1,0+1), (1,0-2), (1+3,0), (1-4,0),
(1,1+5), (1,1-6), (1+7,1), (1-8,1),
(0,1+9), (0,1-10), (0+11,1), (0-12,1), ...

Ha becslést akarunk adni a bolha kezdő pozíciója alapján arra, hogy mennyi idő alatt kapjuk el (t), akkor a következőt mondhatjuk:
4*(max(i,j)-1)^2-4 < t <= 4*(max(i,j))^2-4
Ugyanis az algoritmus a max(i,j)-1 oldalú belső négyzet minden pontját végigellenőrzi fölöslegesen, az origó kivételével mindet 4 időegység alatt, viszont a max(i,j) oldalú négyzeten kívüli pontokat biztosan nem kell már ellenőriznie.