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