Maze Stretching
Labirintdə yol adətən başlanğıc nöqtəsindən son nöqtəyə qədər atılan addımların cəmi kimi hesablanır, burada hər bir addımın məsafəsi dəqiq 1 olaraq qəbul edilir. Gəlin fərz edək ki, labirinti şaquli istiqamətdə (şimal-cənub) "uzada" bilərik, yəni iki hüceyrə arasındakı keçilən məsafəni dəyişə bilərik. Bu halda, məsafə birin əvəzinə X olur. İki ölçülü labirintimiz var və burada divarlar üçün '#', başlanğıc hüceyrəsi üçün 'S' və son hüceyrə üçün 'E' istifadə olunur.
Xarici şərtlərə görə, ən qısa yolun uzunluğunun dəqiq L olmasını təmin etməliyik.
Labirintin konfiqurasiyasını dəyişdirmək və ya üfüqi ölçüsünü dəyişmək icazəli deyil. Yalnız şaquli ölçünü uzatmağa icazə verilir və bu, istənilən faizlə edilə bilər.
Labirintin ən qısa yolunun dəqiq L olması üçün uzatma faizi P-ni tapın.
Girişin ilk sətri test hallarının sayını ehtiva edir. Hər bir test halı üçün əvvəlcə L və N rəqəmləri verilir, burada L ən qısa yolun tələb olunan uzunluğu və N labirinti təsvir edən sətirlərin sayıdır. Sonrakı N sətir labirinti təsvir edir, belə ki, hər bir sətir labirintin bir sıranı təsvir edir. (Hər bir sıranın uzunluğu labirintin üfüqi ölçüsüdür).
Hər bir test halı üçün uzatma faizini aşağıdakı formatda çıxarın:
Case #K: P%
P 0 ilə 1 arasında olduqda ön sıfır olmalıdır.
P 3 ondalığa yuvarlanmalı və həmişə 3 ondalıqda formatlanmalıdır (lazım olduqda son sıfırlarla).
Məhdudiyyətlər
Labirintin hündürlüyü və eni maksimum 100 hüceyrədir.
Bir labirinti təsvir edən bütün sətirlər eyni ölçüdədir.
Həmişə bir həll olacaq.
Nəticə 0.000 və 1000.000 arasında olacaq.
'S' və 'E' arasında birbaşa üfüqi yol olmayacaq. (nəticə həmişə unikaldır).
Birinci test halının izahı: Orijinal labirintdə ən qısa yolun uzunluğu 3-dür, çünki iki üfüqi addım və bir şaquli addım var. Məqsədimiz ən qısa yolun uzunluğunu 2.5 etməkdir. Buna görə də labirintin şaquli ölçüsünü 100-dən az faiz dəyəri ilə "uzatmalıyıq". Bu halda, bu 50%-dir ki, bu da əslində iki hüceyrə arasındakı şaquli məsafəni 0.5-ə dəyişir.
