Розтягування Лабіринту
Зазвичай шлях у лабіринті визначається як сума кроків, зроблених від початкової точки до кінцевої, де відстань одного кроку дорівнює 1. Уявімо, що ми можемо "розтягнути" (скорочувати або подовжувати) лабіринт у вертикальному напрямку (північ-південь). При розтягуванні ми просто змінюємо пройдену відстань між двома клітинками, так що вона стає X замість одиниці. У нас є двовимірний лабіринт, де '#' позначає стіни, 'S' - початкову клітинку, а 'E' - кінцеву клітинку.
Через зовнішні умови, нам потрібно, щоб найкоротший шлях мав точну довжину L.
Ми не можемо змінювати конфігурацію лабіринту або вносити зміни в горизонтальному напрямку. Ми можемо лише розтягувати вертикальний вимір, і це можна зробити на будь-який відсоток.
Знайдіть відсоток розтягування P, при якому найкоротший шлях у лабіринті буде точно L.
Перша строка введення містить кількість тестових випадків. Для кожного тестового випадку спочатку даються два числа L і N, де L - це необхідна довжина найкоротшого шляху, а N - кількість рядків, що описують лабіринт. Наступні N рядків описують лабіринт, причому кожен рядок представляє рядок лабіринту. (Кожна довжина рядка є горизонтальним виміром лабіринту).
Для кожного тестового випадку виведіть відсоток розтягування у наступному форматі:
Випадок #K: P%
P повинно мати провідний нуль, якщо число знаходиться між 0 і 1.
P повинно бути округлене до 3 десяткових, і завжди форматоване на 3 десяткових (з додатковими нулями, якщо потрібно).
Обмеження
Висота і ширина лабіринту максимум 100 клітинок.
Усі рядки, що описують один лабіринт, мають однаковий розмір.
Завжди буде рішення.
Результат буде між 0.000 та 1000.000 включно.
Не буде прямого горизонтального шляху, що з'єднує 'S' та 'E'. (результат завжди унікальний).
Пояснення до першого тестового випадку в прикладі: В оригінальному лабіринті довжина найкоротшого шляху дорівнює 3, оскільки є два горизонтальні кроки і один вертикальний. Наша мета - зробити так, щоб довжина найкоротшого шляху була 2.5. Тому ми повинні "розтягнути" вертикальний вимір лабіринту на відсоткове значення менше 100. У цьому випадку це 50%, що фактично змінює вертикальну відстань між двома клітинками на 0.5.
