GSM hálózat építése nagyon költséges és komplex feladat. Továbbá miután a fő átjátszó állomásokat (BTS) felépítették, azok dolgozni kezdenek, több tényező vizsgálata szükséges a hálózat állapotának vizsgálatához és a teljesítménynövelést célzó javaslatokhoz.Az ACM technikusainak az elektro-mágneses mező erősségének méréséhez speciális felszerelésük van, amellyel az átjátszó állomások jeleinek erősségét és minőségét mérik. A felszerelést egy hatalmas hátizsákba csomagolták, a technikusoknak ezt magukkal kell vinniük egyik átjátszótól a másikig. Sajnos a hátizsák nem olyan nagy, hogy az összes mérési eredményt tárolni képes memóriát szerelhessenek az eszközbe. A hátizsákban egy kisméretű átmeneti tároló van, amely az értékeket csupán néhány másodpercig őrzi. Ekkorra minden adatot továbbítani kell a BTS-nek egy infraport (IRDA) segítségével. Az infraport közvetlen láthatóságot igényel a technikus és a BST között.
Feladat:
Feladatod megkeresni az utat két BTS között, hogy legalább egy BTS minden pillanatban látható legyen.Bemenet:A bemeneti állomány első sorában egy pozitív egész szám (T) van. Ez az állományban található tesztesetek számát adja meg. Minden teszteset egy város leításából áll. Az egyszerűség kedvéért a várost egy téglalap alakú, PxQ méretű táblázattal modellezzük. Minden mező pontosan 1 méter széles. Minden mező egyetlen negatív számot (Zi,i) tartalmaz, a terep adott helyen mért tengerszint feletti magasságát. Tehát a város kockákból építjük fel.Kimenet:A teszteset első sora a város méretét adó P és Q egészeket tartalmazza. (1 <= P, Q <= 200) Az ezt követő P sor mindegyike Q egészet tartalmaz, sszóközökkel elválasztva. A magasság nem nagyobb 5000-nél. (0<=Zi,j<=5000) A terep leírását a teszteset utolsó sorában négy egész szám R1, C1, R2, C2 követi, amelyek két BTS pozícióját adják meg. (1<=R1, R2<=P és 1<=C1, C2<=Q) Az első koordináta a sor, a második az oszlop számát adja meg.
A technikusok lépésenként mozognak. Egy lépés egy mezőről a szomszédos mezőre visz Észak, Kelet, Dél vagy Nyugat irányban. Átlósan nem lehet lépni. Az A mezőről a B mezőre akkor léphetünk, ha a B terület magassága nem nagyon tér el az A terület magasságától. Egy technikus 1 méter úton legfeljebb 3 métert tud leküzdeni.
Minden lépést követően legalább egy BTS-nek látszania kell. Azonban a lépés során lehet olyan pozíció, amelyre ez nem teljesül. Ez idő alatt az adat a cache-ben van. Egy BTS látható, ha a technikus által elfoglalt kockáról látszik a BTS kockája. Egy kockáról a másik akkor látszik, ha a közepüket összekötve más kocka nem metszi a szakaszt. (Az értintés nem számít metszésnek.) A technikus és a BTS is fél méterrel a felszín felett van.
Példa:
direct.in direct.ans 4
5 5
8 7 6 5 4
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
1 1 5 1
5 8
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
9 9 9 9 9 9 9 2
2 2 2 2 2 2 2 2
1 2 5 1
5 8
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
9 9 9 9 9 9 9 2
2 2 2 2 2 2 2 2
1 5 5 1
6 12
5 5 5 5 1 5 5 5 5 5 5 5
5 5 5 5 1 5 5 5 5 5 5 5
5 5 5 5 9 5 5 5 5 5 5 5
5 9 1 5 5 5 5 5 5 5 5 5
5 5 9 5 5 5 5 5 5 5 5 5
5 5 9 5 5 5 5 5 5 5 5 5
6 1 3 12The shortest path is 10 steps long.
Mission impossible!
The shortest path is 14 steps long.
The shortest path is 18 steps long.