Коров'яча навігація#10552
Бессі знову опинилася не з того боку ферми Фермера Джона, і, оскільки вона дуже погано бачить, їй потрібна ваша допомога, щоб пройти через ферму.
Ферма представлена квадратною сіткою n \times n клітинок, деякі з яких порожні, а деякі містять непрохідні тюки сіна. Бессі починає рух з нижнього лівого кута (клітинка ) і хоче дістатися до верхнього правого кута (клітинка ). Ви можете керувати її рухом, задаючи послідовність команд, кожна з яких є однією з наступних: «вперед», «повернути ліворуч на градусів» або «повернути праворуч на градусів». Потрібно задати найкоротшу можливу послідовність команд, яка приведе її до місця призначення.
Якщо ви даєте Бессі команду рухатися за межі сітки (тобто в стіну ферми) або в тюк сіна, вона не переміщується і просто переходить до виконання наступної команди в послідовності.
На жаль, Бессі не знає, у якому напрямку вона спочатку дивиться: вгору (у бік клітинки ) чи праворуч (у бік клітинки ). Вам необхідно задати найкоротшу можливу послідовність команд, яка приведе Бессі до мети незалежно від її початкового напрямку. Щойно вона досягне мети, вона проігнорує всі команди, що залишилися.
У першому рядку міститься число n~(2 \le n \le 20). Кожен із наступних рядків містить рядок рівно з символів, що описує ферму. Перший символ останнього рядка відповідає клітинці , а останній символ першого рядка відповідає клітинці .
Кожен символ дорівнює або , що позначає тюк сіна, або , що позначає порожню клітинку.
Гарантується, що клітинки та є порожніми. Крім того, гарантується, що існує шлях, який складається лише з порожніх клітинок, з клітинки до клітинки .
Виведіть довжину найкоротшої послідовності команд, яка приведе Бессі до мети незалежно від того, чи починає вона рух, дивлячись вгору чи праворуч.
У цьому прикладі послідовність команд "Forward, Right, Forward, Forward, Left, Forward, Left, Forward, Forward" приведе Бессі до місця призначення незалежно від її початкового напрямку.
Приклад 1