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