Egy föld alatti barlangrendszerben kajakozol, amikor rádöbbensz, hogy érkezik a dagály, ezért csapdába kerültél. Szerencsére van egy térképed a barlangról. Egészen addig várnod kell, amíg elkezdődik az apály, ezért lesz időd átgondolni, hogy mi lesz a leggyorsabb módja a menekülésnek (az apály kezdetétől számolva). A barlang térképe két N x M-es táblázatból áll. Az első a plafon magasságát adja meg minden "cellában", a második pedig a padló magasságát. A padló olyan anyagból van, hogy átereszti a vizet, ezért a vízszint csökkenésekor sehol nem marad víz a vízszint felett, akkor sem, ha a padló magasabban van. A térkép észak-nyugati sarkában estél csapdába. Pillanatnyilag H centiméter a víz magassága, ami az apály kezdetétől másodpercenként 10 cm-rel csökken, amíg el nem éri a 0-át. A kijárat a dél-keleti sarokban van, ami pillanatnyilag víz alatt áll, de az apály kezdete után járhatóvá válik. Bármely pillanatban négy irányba tudsz lépni, (É, K, D, NY) a következő feltételek mellett:
![]()
Ha egy mezőről olyankor lépsz át a szomszédosra, amikor az aktuális mezőn még legalább 20 cm víz van a padló szintje fölött, akkor 1 másodperc alatt átérsz a szomszédos mezőre (használhatod a kajakot). Egyébként 10 másodperc egy lépés, mert kézben kell vinned a kajakodat. Ez az idő csak a kiindulási mező vízszintjétől függ. Egy ideig el fog tartani, amíg a víz apadni kezd, és addig tetszőlegesen mozoghatsz a barlangban. Csak az számít, hogy az apály kezdetétől számítva mennyi idő kell a szabaduláshoz. Ki tudod ezt számítani? Megjegyzés Elképzelhető, hogy végig tudsz menni a teljes barlang-rendszeren az apály kezdete előtt. Ebben az esetben a kijáratnál várhatod meg a vízszint csökkenését, és így 0 idő alatt kijutsz, az apály kezdetétől számolva. FeladatÍrjunk programot, ami megadja, hogy az apály kezdetétől számolva mennyi idő kell ahhoz, hogy kijussunk a barlangból.
Bemenet
KimenetMinden tesztesethez egyetlen (tört) számot kell megadni, ami akkor helyes, ha legfeljebb 10-6 az eltérése a pontos választól. MéretekKis bemenet1 ≤ T ≤ 50. Nagy bemenet1 ≤ T ≤ 50. 1 ≤ Fxy ≤ Cxy ≤ 10000. Példa
TesztadatokCímkékA feladat forrása: Google Code Jam 2012, Round 1B, https://code.google.com/codejam/contest/1836486/dashboard#s=p1
Algoritmusok: Dijkstra-algoritmus
megoldás |
Programozás > Feladatok >