Телепортуватися геть!
Ви перебуваєте в прямокутному лабіринті і прагнете якомога швидше його залишити. Лабіринт представлений у вигляді прямокутної сітки квадратних клітинок. Деякі клітинки заблоковані, а інші є виходами. Якщо ви потрапите на клітинку з виходом, ви можете негайно покинути лабіринт.
Ви можете переміщатися на одну клітинку за раз, на одну з сусідніх клітинок. Дві клітинки вважаються сусідніми, якщо вони мають спільну сторону. Тобто, ви можете рухатися лише на одну клітинку вгору, вниз, вправо або вліво. Звісно, ви не можете вийти за межі лабіринту і не можете ступити на заблоковану клітинку.
Крім того, на будь-якому кроці ви можете скористатися своїм телепортом. Цей пристрій перенесе вас у випадкову незаблоковану клітинку всередині лабіринту з рівною ймовірністю (включаючи, можливо, ту, на якій ви зараз стоїте!). Якщо пристрій випадково перенесе вас на клітинку, яка також є виходом, ви негайно покинете лабіринт. Ура!
Єдиний спосіб покинути лабіринт - це потрапити на вихід (або телепортом, або пішки), ви не можете вийти за межі лабіринту. Напишіть програму, щоб обчислити очікувану кількість кроків, необхідних для виходу з лабіринту. Припустимо, що ви будете обирати свої дії (рухи та використання телепорту) оптимально, щоб мінімізувати очікувану кількість кроків для виходу з лабіринту. Використання телепорту вважається одним кроком.
Вхідні дані
Буде декілька тестових випадків. Кожен тестовий випадок починається з рядка, що містить два додатні цілі числа R та C (R <= 200, C <= 200). Потім наступні R рядків кожен містить C символів, що представляють клітинки в лабіринті. Символи будуть одним з наступних:
E: представляє вихід, у кожному лабіринті буде принаймні один 'E'.
Y: представляє ваше початкове місце, у кожному лабіринті буде рівно один 'Y'.
X: представляє заблоковане місце.
.: представляє порожнє місце.
Ви можете рухатися/телепортуватися на будь-яке місце, позначене 'E', 'Y' або '.'.
Кінець вводу позначається рядком з двома розділеними пробілом 0.
Вихідні дані
Для кожного тестового випадку виведіть один рядок, що містить мінімальну очікувану кількість кроків, необхідних для виходу з лабіринту, за умови, що ви робите свої вибори оптимально, щоб мінімізувати це значення. Виведіть ваш результат з точністю до 3 десяткових знаків. Не друкуйте жодних порожніх рядків між виходами.