Programozás‎ > ‎Feladatok‎ > ‎

Dagály és apály

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 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:

  • A vízszint, az aktuális mező padlójának szintje és a szomszédos mező padlójának szintje legalább 50 cm-rel kevesebb mint a szomszédos mező plafonjának szintje. Megjegyzés: ez azt jelenti, hogy olyan mezőre sosem tudunk lépni, amelynek plafonja és padlója között 50 cm-nél kevesebb a távolság. 
  • A szomszédos mező padlója legalább 50 cm-rel lejjebb van, mint az aktuális mező plafonja.
  • A térképről nem szabad lelépni.
Jegyezzük meg, hogy a feltételek teljesülése esetén bármennyit tudsz lefelé és felfelé menni a kajakkal (egész jól megerősödtél az evezéstől). Akár az is lehet, hogy egy 10 cm magasságban lévő mezőről egy 9000 cm magasságban lévő mezőre mászol fel. A következő ábra a feltételek illusztrálására szolgál: 

  • Az első ábrán nincs meg az 50 cm a szomszédos plafon és a vízszint között, ezért nem tudsz átlépni. 
  • A második ábrán az a baj, hogy a szomszédos plafon és az aktuális padló között nincs meg az 50 cm.
  • A harmadik ábrán a szomszédos mező plafonjának és padlójának távolsága túl kicsi. Egy ilyen mezőre soha nem tudunk rálépni, a vízszinttől függetlenül.
  • A negyedik ábrán azért nem tudsz jobbra lépni, mert az aktuális plafon és a szomszédos padló között túl kicsi a távolság. 

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

  • Az első sor a tesztesetek T számát tartalmazza.
  • Ezután T teszteset következik, amelyek mindegyike egy három számot tartalmazó sorral kezdődik: HN és M, a kezdeti vízszint, és a térkép dimenziói. A következő 2N sor a padló és a plafon magasságot adja meg az alábbiak szerint:
    • Először  N sor mindegyike  M szóközökkel elválasztott egészt tartalmaz. A j. szám az i. sorban Cij, a plafon magassága a (j, i) koordinátájú cellában. (Az i dél felé, a j kelet felé nő.)
    • Ezután  N sorban a padló magasságok (Fji) vannak megadva, az előzővel azonos formátumban.
  • A kiinduló mezőn kezdetben biztosan lesz 50 cm a vízszint és a plafon, illetve a padló és a plafon között.
  • A kijáratnál lesz legalább 50 cm a padló és a plafon között.
  • Mindig lesz kiút (elvégre valahogy be is jutottál a barlangba).

Kimenet

Minden 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éretek

Kis bemenet

1 ≤ T ≤ 50. 
1 ≤ N, M ≤ 10. 
1 ≤ H ≤ 1000. 
1 ≤ Fxy ≤ Cxy ≤ 1000.

Nagy bemenet

1 ≤ T ≤ 50. 
1 ≤ N, M ≤ 100. 
1 ≤ H ≤ 10000. 

1 ≤ Fxy  Cxy ≤ 10000.

Példa

Bemenet  Kimenet
4
200 1 2
250 233
180 100
100 3 3
500 500 500
500 500 600
500 140 1000
10 10 10
10 10 490
10 10 10
100 3 3
500 100 500
100 100 500
500 500 500
10 10 10
10 10 10
10 10 10
100 2 2
1000 1000
1000 1000
100 900
900 100
Case #1: 11.7
Case #2: 3.0
Case #3: 18.0
Case #4: 0.0



Tesztadatok

Címkék

A feladat forrása: Google Code Jam 2012, Round 1B, https://code.google.com/codejam/contest/1836486/dashboard#s=p1
Algoritmusok: Dijkstra-algoritmus

megoldás