Застряглий робот
Робот застряг серед уламків міжзоряного космічного корабля. Десь серед цих уламків є телепорт, який може доставити робота в безпечне місце.
Космічний корабель втратив контроль по всіх осях. Найближча зірка освітлює уламки, а корабель оснащений генератором штучної гравітації. Штучна гравітація завжди відводить робота від зірки, незалежно від орієнтації корабля.
Робот має сонячні панелі і повинен використовувати сонячну енергію для переміщення серед уламків. Якщо уламки затуляють зірку, робот не може рухатися. Проте, після кожного руху робот закріплюється і не ризикує розбитися або впасти в космічну порожнечу.
Уламки та простір навколо них представлені тривимірною сіткою a розміру m * n * p. Кожен блок може бути частиною корабля або порожнім. Блоки корабля можуть бути роз'єднані.
Робот починає, прикріплений до частини корабля, і сам вирішує, коли рухатися, а коли чекати, поки зірка не освітить зручний бік.
Більш формально, гравітація може тягнути робота в одному з 6 напрямків: 2 напрямки вздовж кожної з 3 осей. Клітинка освітлена зіркою, якщо немає уламків у напрямку, протилежному силі тяжіння. Перед кожним рухом робот може обирати напрямок, в якому його притягує сила тяжіння. Під час руху і початкова, і кінцева позиції повинні бути освітлені зіркою.
Дозволені такі ходи: (світло завжди падає зверху на зображеннях; синій блок (або темніший у чорно-білих версіях) представляє робота, а оранжеві блоки (або світліші) - можливі пункти призначення)
Переміщення по підлозіЯкщо робот стоїть на вершині блоку, він може переміститися в сусіднє положення, за умови, що воно на тій самій висоті.
Робот не може рухатися по діагоналі. Пункт призначення також повинен бути освітлений зіркою.
Стрибок з обривуРобот може зробити крок з підвищення і потім впасти. Немає обмежень щодо тривалості падіння.
Робот не може впасти в космічну порожнечу або в неосвітлене місце.
Падіння внизЯкщо робот освітлений зіркою і висить, він може впасти. Це може статися, якщо напрямок сили тяжіння змінився.
Робот не може впасти в космічну порожнечу.
Мета полягає в тому, щоб дістатися до телепорту, якщо це можливо, використовуючи найменшу кількість ходів. Щоб телепорт працював, робот повинен бути міцно прикріплений до корабля. Іншими словами, робот повинен опинитися біля телепорту в кінці дозволеного ходу, і спуститися через нього не вийде. Телепорт не блокує ні зірку, ні рух робота.
Вхідні дані
Перша строка містить три цілі числа m, n, p (1 ≤ m, n, p ≤ 500).
Космічний корабель і простір навколо нього описуються p блоками.
k-й блок описує блок, розташований на k-й висоті. Кожен блок складається з n рядків.
i-й рядок k-го блоку складається з m символів. j-й символ називається a[ijk].
Якщо
a[ijk]дорівнює "*", то це повний блок.Якщо
a[ijk]дорівнює "-", то це порожній блок.Якщо
a[ijk]дорівнює "R", то цей блок містить робота. Гарантується, що такий блок тільки один.
Гарантується, що робот знаходиться біля повного блоку.
Якщо
a[ijk]дорівнює "T", то цей блок містить телепорт. Гарантується, що такий блок тільки один.
Вихідні дані
Виведіть мінімальну кількість ходів, необхідну для досягнення телепорту, або -1, якщо телепорт недоступний.