Zombie Partlayışı!#3374
Kömək edin!!! Zombilər irəliləyir! Zombi hücumu başlayıb və onların legionu müdafiəmizin son xəttinə doğru irəliləyir.
Lakin bütün ümidlər itirilməyib. Gələcək fəlakəti nəzərə alaraq, siz döyüş meydanına Tənzimlənən Yanğın Minaları (TYM) yerləşdirmisiniz. Siz bu minaların hamısını eyni anda partladaraq idarə etdiyiniz bir partlayış radiusu ilə partlada bilərsiniz və hər mina partlayış radiusu daxilində olan hər hansı bir zombini dərhal yandıracaq.
Siz vəziyyətin xəritəsini əldə etmək üçün peyk şəkli çəkirsiniz. Xəritə kvadrat hüceyrələrə bölünmüş düzbucaqlı bir sahədir. Hər bir hüceyrə ya boşdur, ya zombi (Z) tərəfindən tutulmuşdur, ya da mina (M) tərəfindən tutulmuşdur. Məsələn, belə görünə bilər:
Zombi, mərkəzi tutduğu hüceyrənin mərkəzi ilə minanın hüceyrəsinin mərkəzi arasındakı məsafə partlayış radiusuna bərabər və ya ondan az olduqda mina tərəfindən yandırılacaq. Yan təsirləri minimuma endirmək üçün siz minaları bütün zombiləri yandıracaq ən kiçik partlayış radiusu ilə partlatmalısınız. Verilən hücum ssenarisi üçün həmin radius nə qədərdir?
Giriş bir tam ədəd N ilə başlayır, bu, partlayış radiusunu müəyyən etməli olduğunuz hücum ssenarilərinin (xəritələrin) sayını göstərir. Hər bir ssenari iki boşluqla ayrılmış tam ədəd, w və h (1 ≤ w, h ≤ 2000) ilə başlayan bir sətirlə başlayır, bu, xəritənin enini və hündürlüyünü göstərir. Sonra xəritə h sətir mətn kimi gəlir, hər biri w simvoldan ibarət, hər bir hüceyrənin nə ilə tutulduğunu göstərir:
'Z' zombini göstərir
'M' minanı göstərir
'.' boş hüceyrəni göstərir.
Hər bir xəritədə ən azı bir zombi (Z) və bir mina (M) olacaq.
Hər bir hücum ssenarisi üçün, bütün zombiləri yandırmaq üçün minaları partlatmalı olduğunuz ən kiçik partlayış radiusu olan r real ədədini bir sətirdə çıxarın. Çıxışınız dəqiq cavaba nisbətən 10^{-6} faktorundan çox olmayan bir səhvlə dəqiq olmalıdır. (Məsələn, əgər düzgün cavab 50dirsə, 49.99995 ilə 50.00005 arasında olan hər hansı bir cavab qəbul ediləcəkdir.)
Nümunə 1