Амбар описывается решёткой \(N \times N\) (\(2 \leq N \leq 20\)) символов,
некоторые из них пусты, некоторые заняты. Бесси начинает в левом нижнем углу
(1,1) и должна пройти в правый верхний угол \(N,N\). Вы можете управлять ею
посредством последовательности инструкций вида "вперёд", "повернись влево на 90 градусов",
"повернись вправо на 90 градусов".
Вы хотите задать кратчайшую последовательность, которая приведёт ее к цели.
Есл инструкицю выполнить невозможно, Бесси пропускает её и переходит к следующей
инструкции.
К несчастью, Бесси не знает, куда она смотрит вначале в клетку (1,2) или в клетку
(2,1). Вы должны дать такую последовательность, которая приведёт её к цели
кратчайшим образом вне зависимости от того, какой случай произошёл.
Когда Беси достигает цели, она игнорирует остальные команды.
ФОРМАТ ВВОДА (файл cownav.in):
Первая строка ввода содержит
\(N\).
Каждая из \(N\) последующих строк содержит ровно \(N\) символов,
представляющих амбар. Первый символ последней строки есть ячейка (1,1).
Поседний символ первой строки есть ячейка (N,N).
Каждый символ или H (непроходимы стог сена) или E - пустая ячейка.
Гарантируется, что ячейки 1,1 и \(N,N\) будут пустые, также гарантируется
существование пути по пустым ячейкам из 1,1 в \(N, N\).
ФОРМАТ ВЫВОДА (файл cownav.out):
На единственной выводной строке выведите длину кратчайшей последовательности
команд, которая приведёт Бесси к цели, вне зависимости куда она смотри вначале, вверх
или вправо.
ФОРМАТ ВВОДА:
3
EHE
EEE
EEE
ФОРМАТ ВЫВОДА:
9
В этом примере Инструкции "Вперёд, Вправо, Вперёд, Вперёд, Влево,
Вперёд, Влево, Вперёд, Вперёд" приведут Бесси к назначению вне зависимости
от начальной ориентации.
Problem credits: Brian Dean