pamięć: 64MB
W związku ze zbliżającym się końcem świata Ziemię zaatakowały welociraptory (rodzaj niewielkich teropodów z rodziny dromeozaurów). To oczywiście wątek główny nadchodzącego hitu kinowego. W kluczowej scenie ucieczki główny bohater znajduje się w opustoszałym mieście, gdzie czyhają na niego welociraptory. Bohater potrzebuje jednej sekundy by przejść z jednego pola na sąsiednie (o wspólnym boku). Mając dany czas, jakiego potrzebują welociraptory na takie przejście oraz plan miasta z zaznaczonym początkowym położeniem każdego raptora, znajdź najkrótszą drogę, po której niezależnie od (nieznanych bohaterowi) zachowań raptorów będzie można bezpiecznie przejść do wskazanego miejsca.
Wypisz jedną liczbę - długość (w sekundach) najkrótszej drogi z (1,1) do (ex,ey), na której (poruszając się stale o pole na sekundę) na pewno nie napotkamy raptora. Wypisz -1 jeżeli takiej drogi nie ma.
Tu bohater musi przebiec dłuższą, dolną drogą, by uniknąć zjedzenia.
| wejście | wyjście |
|---|---|
4 6 5 3 6 .###w# ...... .####. ...... | 9 |
Tu nawet biegnąc na około zostanie w ostatniej chwili pożarty.
| wejście | wyjście |
|---|---|
4 6 5 2 6 .###w# ...... .####. ...... | -1 |
A tu może czmychnąć tuż przed raptorem.
| wejście | wyjście |
|---|---|
4 6 5 3 6 .##w## ...... .####. ...... | 7 |
[Zgłoś rozwiązanie] [Moje zgłoszenia]