1. .. pdfinfo::
2.   :place: Kraków
3.   :date: 2018-02-05
4.   :contest_name: Olimpijskie Warsztaty Lokalne
5.   :contest_date: Poniedziałek
6.   :leftlogo: owl.png
7.   :rightlogo: tcs.pdf
8.  
9. Miodek
10. =====================
11.  
12. Kubuś Puchatek znalazł sekretny pszczeli skarb - miodek! Właśnie w najlepsze zajadał sobie ów miodek, gdy nagle został zauważony przez jedną z pszczół, a ta wszczęła pszczeli alarm.
13. Kubuś pomimo, że jest misiem o bardzo małym rozumku, zdaje sobie sprawę, że w tym samym momencie hordy pszczół zaczęły wylatywać z uli i rozprzestrzeniać się, starając się go złapać. Wie, że musi zostawić miodek i uciekać do swojego domku, ale miodek jest tak pyszny... że Kubuś nie chce zacząć uciekać przedwcześnie.
14. Pomóż misiowi określić ostatni możliwy moment, w którym może porzucić miodek.
15.  
16. Las, w którym rzecz się dzieje, jest przedstawiony jako kwadrat podzielony "w kratkę" na :math:`N` x :math:`N`kwadratów jednostkowych, o bokach ułożonych w kierunkach północ-południe i wschód-zachód.
17. W każdym z kwadratów jednostkowych znajduje się drzewo, trawa, ul lub domek Kubusia Puchatka.
18. Dwa kwadraty jednostkowe nazwiemy sąsiednimi, jeśli jeden z nich styka się z drugim bezpośrednio od północy, południa, wschodu lub zachodu (ale nie po przekątnej).
19. Kubuś nie porusza się zbyt zgrabnie - każdy jego krok musi prowadzić do sąsiedniego kwadratu jednostkowego. Kubuś może chodzić tylko po trawie, a nie potrafi przedzierać się przez drzewa ani ule. Ponadto, w ciągu minuty może wykonać co najwyżej :math:`S` kroków.
20.  
21. W chwili, gdy pszczoły wszczęły alarm, Kubuś stoi w trawiastym kwadracie jednostkowym, w którym znajduje się miodek, a pszczoły znajdują się w każdym kwadracie jednostkowym zawierającym ul (w lesie może być więcej niż jeden ul). Od tej chwili, w ciągu każdej minuty dzieją się następujące rzeczy, w podanej kolejności:
22.  
23. Jeśli Kubuś wciąż zajada miodek, musi zdecydować, czy kontynuować wyżerkę, czy też zacząć uciekać. Jeśli postanawia jeść nadal, to do końca minuty nie przemieszcza się. W przeciwnym razie natychmiast zaczyna uciekać i wykonuje co najwyżej :math:`S` kroków, zgodnie z podanymi powyżej zasadami. Kubuś nie może zabrać ze sobą miodku, więc jak tylko zacznie uciekać, przestaje jeść miodek.
24.  
25. Po tym, jak Kubuś przełknie już miodek jedzony w danej minucie lub wykona wszystkie kroki w danej minucie, pszczoły rozprzestrzeniają się o jeden kwadrat jednostkowy, ale tylko na trawiaste kwadraty jednostkowe.
26. Dokładniej, pszczoły rozprzestrzeniają się na każdy trawiasty kwadrat jednostkowy, który sąsiaduje z kwadratem jednostkowym już zajętym przez pszczoły. Co więcej, jeśli w jakimś kwadracie znajdują się pszczoły, to będą się tam już zawsze znajdować (czyli rój pszczół nie przemieszcza się, tylko rozprzestrzenia).
27.  
28. Inaczej mówiąc, pszczoły rozprzestrzeniają się w następujący sposób. Gdy zostaje wszczęty alarm, pszczoły zajmują tylko te kwadraty, w których są ule. Pod koniec pierwszej minuty zajmują również wszystkie trawiaste kwadraty jednostkowe przylegające do uli. Pod koniec drugiej minuty zajmują również wszystkie trawiaste kwadraty jednostkowe przylegające do trawiastych kwadratów jednostkowych przylegających do uli, itd. Po odpowiednio długim czasie pszczoły zajmą wszystkie trawiaste kwadraty jednostkowe, do których uda im się dotrzeć.
29.  
30. Ani Kubuś Puchatek, ani pszczoły nie mogą opuścić lasu. Zauważ, że zgodnie z podanymi zasadami, Kubuś będzie zajadał miodek przez całkowitą liczbę minut.
31.  
32. Pszczoły dopadają misia, jeśli w jakimkolwiek momencie Kubuś znajduje się w kwadracie jednostkowym zajętym przez pszczoły.
33.  
34. Wejście
35. -------
36. Napisz program, który na podstawie danej mapy lasu określi maksymalną liczbę minut, przez które Kubuś Puchatek może zajadać miodek, tak żeby nadal mógł uciec do swojego domku, zanim dopadną go pszczoły.
37.  
38. Twój program powinien wczytać ze standardowego wejścia następujące dane:
39.  
40. W pierwszym wierszu znajdują się dwie liczby całkowite :math:`N (1 \leq N \leq 800)` i :math:`S (1 \leq S \leq 1000` , oddzielone pojedynczym odstępem.
41. Kolejne :math:`N` wierszy zawiera opis mapy lasu. Każdy z tych wierszy zawiera :math:`N` znaków, a każdy znak przedstawia jeden kwadrat jednostkowy. Możliwe znaki i ich znaczenia są następujące:
42.  
43. :math:`T` oznacza drzewo,
44. :math:`G` oznacza trawę,
45. :math:`M` oznacza początkowe położenie misia Mecho oraz miodku, znajdujące się na trawie,
46. :math:`D` oznacza domek Kubusia Puchatka, w którym Kubuś może się skryć, a pszczoły nie mają do niego wstępu,
47. :math:`H` oznacza ul.
48.  
49. Możesz założyć, że na mapie znajduje się dokładnie jedna litera :math:`M`, dokładnie jedna litera :math:`D` i przynajmniej jedna litera :math:`H`. Możesz również założyć, że istnieje ciąg sąsiadujących ze sobą liter :math:`G` łączących Kubusia z jego domkiem, a także ciąg sąsiadujących ze sobą liter :math:`G` łączących przynajmniej jeden z uli z miodkiem (czyli początkowym położeniem misia). W szczególności, każdy z tych ciągów może być pusty - gdy domek misia lub ul sąsiaduje z miodkiem. Zwróć uwagę, że pszczoły nie mogą przelecieć przez domek misia ani nad nim. Jest on dla nich niczym drzewo.
50.  
51. W testach wartych :math:`40` punktów :math:`N` zachodzi :math:`N \leq 60`.
52.  
53. Wyjście
54. -------
55. Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający jedną liczbę całkowitą: maksymalną liczbę minut, przez które Kubuś Puchatek może zajadać miodek, znajdując się w swoim początkowym położeniu, tak aby nadal mógł uciec do swojego domku, zanim dopadną go pszczoły.
56.  
57. Jeśli Kubuś w ogóle nie ma szansy uciec do domku, zanim dopadną go pszczoły, Twój program powinien zamiast tego wypisać na standardowe wyjście liczbę :math:`-1`.
58.  
59. **Dostępna pamięć: 128MB**
60.  
61. Przykład
62. --------
63.  
64. .. list-table::
65.  :header-rows: 1
66.  
67.  * - Dla danych wejściowych:
68.    - Poprawną odpowiedzią jest:
69.  * - ::
70.  
71.        7 3
72.        TTTTTTT
73.        TGGGGGT
74.        TGGGGGT
75.        MGGGGGD
76.        TGGGGGT
77.        TGGGGGT
78.        THHHHHT
79.        
80.    - ::
81.  
82.        1
83.  
84.  * - ::
85.  
86.        7 3
87.        TTTTTTT
88.        TGGGGGT
89.        TGGGGGT
90.        MGGGGGD
91.        TGGGGGT
92.        TGGGGGT
93.        TGHHGGT
94.  
95.    - ::
96.  
97.        2
98.  
99. Wyjaśnienie do przykładu
100. ------------------------
101.  
102. W przykładzie pierwszym Kubuś może zajadać miodek przez minutę, po czym może uciekać najkrótszą drogą, prosto na prawo, i po dwóch minutach będzie bezpieczny w domku.
103.  
104. Zaś w przykładzie drugim Kubuś może zajadać miodek przez dwie minuty, w trzeciej minucie może wykonać kroki w prawo, w górę, w prawo, w czwartej minucie kroki w prawo, w prawo, w prawo i w piątej minucie kroki w dół i w prawo.