Сусіднє село
Limits: 2 sec., 256 MiB
А тим часом Андрій Старобувний святкував свої іменини: зібралися вони з друзями та й поїхали в сусіднє село. Добряче відсвяткувавши, Андрійко попрощався і вирішив прямувати додому. Але це виявилось не так і просто — чи то через втому, чи то пива (чи чим то там у тому селі святкують?) було трішки забагато, а втім, наш герой зовсім забув, у який бік йому йти. Добре, що він завбачливо взяв із собою карту, на якій були позначені дороговкази, що мали б вивести з чужого села. Отак помалу прямуючи до першого вказівника, Андрій задумався над тим, скільки ж йому доведеться пройти, поки він не покине межі чужого села?..
Карта в іменинника прямокутна, розділена на одиничні квадрати. Кожен квадрат може містити інформацію про те, в якому напрямі треба рухатися, щоб вийти з села. Як тільки Андрій попадає у квадрат з вказівником, він обов’язково слідує у вказаному напрямі, поки не зустріне інший вказівник або не вийде за межі села.
Вам дано цю карту і початкове місцезнаходження Андрія. Напишіть програму, яка визначить відстань, що необхідно пройти нашому герою, щоб покинути чуже село.
Input
У першому рядку задано два цілі числа — висоту карти \(n\) та ширину \(m\).
У наступних рядках міститься опис карти. При цьому .
(крапка) означає, що в цьому квадраті немає вказівника, U
—
потрібно йти на північ, щоб вийти з села, D
— потрібно йти
на південь, L
— на захід, R
— на схід.
Місцезнаходження Андрія позначається на карті буквою M
і
у квадраті, в якому він стоїть, немає ніякого вказівника.
Початково Андрій прямує на схід.
Output
Виведіть відстань (кількість квадратів), яку повинен пройти Андрій,
поки не вибереться з села, або -1
, якщо йому це не
вдасться.
Constraints
\(1 \le n, m \le 100\).
Samples
Input (stdin) | Output (stdout) |
---|---|
4 3 ..L ... M.U ... | 7 |
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|