Помилковий робот#8202
Ви намагаєтеся запрограмувати робота, щоб він міг рухатися по двовимірному лабіринту і знайти вихід.
Лабіринт представлений у вигляді сітки з рядків і стовпців. Деякі клітинки містять перешкоди, які робот не може пройти; інші клітинки є порожніми, і робот може рухатися через них вільно. Лише одна з порожніх клітинок позначена як вихід; робот негайно покидає лабіринт, як тільки досягає цього місця.
Ви можете керувати роботом, надіславши йому командний рядок, що складається з символів L, U, R, D, які відповідають напрямкам ліворуч, вгору, праворуч, вниз відповідно. Після отримання команд робот почне виконувати їх, переміщуючись у сусідню клітинку у вказаних напрямках. Якщо робот натрапить на перешкоду або край сітки, він проігнорує цю команду, але продовжить виконувати інші. Робот також ігноруватиме всі команди після досягнення виходу.
Ваш друг надіслав вам певний командний рядок, але ви швидко зрозуміли, що цей рядок не обов'язково приведе робота до виходу. Ви хочете виправити рядок так, щоб робот досяг виходу. За одну секунду ви можете видалити будь-який символ або додати новий символ у будь-яке місце. Визначте, як швидко ви можете виправити командний рядок вашого друга.
Вам не важливо, скільки часу займе шлях робота до виходу. Вам слід мінімізувати час, необхідний для виправлення командного рядка.
Перший рядок містить два цілих числа і (1 \le n, m \le 50).
Кожен з наступних рядків містить символів, що описують сітку. Порожні клітинки позначаються символом `.'. Початкове положення робота позначено як R, перешкоди як #, вихід як E.
Наступний і останній рядок містить командний рядок вашого друга, що складається від до символів включно.
Гарантовано, що лабіринт містить рівно одну R і одну E, причому завжди існує шлях від R до E.
Виведіть одне ціле число — мінімальний час, необхідний для виправлення програми.
Приклад 1
Приклад 2