eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Змейка

Змейка

Лимит времени 3 секунды
Лимит использования памяти 64 MiB

Всем известно, что нелегко живётся змейкам в лабиринтах. Даже если змейка одна в лабиринте, она может погибнуть, врезавшись в стену или в свой хвост. Некто Вася, претендент на победу в конкурсе змеек, решил научить свою змейку выбираться из опасных частей лабиринта. Опасность таких «подлабиринтов» в том, что шансы змейки выбраться оттуда живой малы, и, конечно, чем длиннее змейка, тем ниже шансы. Вася проводит обучение змейки так: в юном возрасте, когда длина змейки достигает 2, Вася запускает змейку в тренировочный опасный лабиринт; цель змейки— выбраться оттуда как можно быстрее, если она выживает, то по достижении длины 3 обучение повторяется в том же лабиринте, и так пока змейка не станет совершенно длинной (длины 18) либо не погибнет.

Лабиринт можно представить себе как прямоугольник ширины W и длины H, каждая клетка которого — либо препятствие 'X', либо свободное место '.'. Лабиринт окружён непроходимыми камнями '*', за исключением одной клетки '#', смежной входу в лабиринт, который расположен на границе лабиринта. Вот, например, простой лабиринт длины 4 и ширины 3:

Змейка длины L представляет собой последовательность из L клеток. Каждая клетка последовательности смежна с соседними клетками по стороне. Все клетки в последовательности различны. Змейка может ползти относительно текущего направления движения в трёх направлениях: прямо, налево или направо. Змейка ползёт одновременно всем телом, и каждая клетка, кроме первой, занимает место предыдущей. Вот примеры допустимых движений змейки:

321. -> .321

321 -> .32

... ..1

12 -> 23

.3 1.

12 -> 23

43 14

Змейка за каждую единицу времени проползает ровно одну клетку, если же ей некуда ползти, то она погибает.

Входные данные

В первой строке находятся размеры лабиринта H и W (1H300, 1W30). Во второй строке находятся координаты входа h_0 и w_0. Причем либо h_0 = 1, либо h_0 = H, либо w_0 = 1, либо w_0 = W. Далее следуют H строк по Wсимволов — построчное описание лабиринта, где 'X' обозначает препятствие, а '.' свободную клетку. Отсчёт времени начинается с 0; начальное положение змейки: голова в точке (h_0, w_0), остальная часть тела снаружи. Отсчёт времени заканчивается, когда голова змейки вновь окажется в клетке (h_0, w_0). И ещё, лабиринт хоть и тренировочный, но ни одна змейка длины 18 не может выбраться оттуда живой.

Выходные данные

Выход должен содержать 16 строчек, где i-я строчка представляет собой лучшее время, за которое змейка длиныi+1 может выбраться из лабиринта, либо −1, если она неминуемо погибает.

Пример

Входные данные #1
9 9
1 5
XXXX.XXXX
XXX...XXX
XX..X..XX
....XX..X
X.X.X.X.X
..XX.....
X...XXX..
XXXXX....
X.....XXX
Выходные данные #1
10
10
10
22
22
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
Автор Дмитрий Иванков
Источник Petrozavodsk summer training camp, August 2005