Змейка
Всем известно, что нелегко живётся змейкам в лабиринтах. Даже если змейка одна в лабиринте, она может погибнуть, врезавшись в стену или в свой хвост. Некто Вася, претендент на победу в конкурсе змеек, решил научить свою змейку выбираться из опасных частей лабиринта. Опасность таких «подлабиринтов» в том, что шансы змейки выбраться оттуда живой малы, и, конечно, чем длиннее змейка, тем ниже шансы. Вася проводит обучение змейки так: в юном возрасте, когда длина змейки достигает 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 (1 ≤ H ≤ 300, 1 ≤ W ≤ 30). Во второй строке находятся координаты входа 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, если она неминуемо погибает.