Всем известно, что нелегко живётся змейкам в лабиринтах. Даже если змейка одна в лабиринте, она может погибнуть, врезавшись в стену или в свой хвост. Некто Вася, претендент на победу в конкурсе змеек, решил научить свою змейку выбираться из опасных частей лабиринта. Опасность таких «подлабиринтов» в том, что шансы змейки выбраться оттуда живой малы, и, конечно, чем длиннее змейка, тем ниже шансы. Вася проводит обучение змейки так: в юном возрасте, когда длина змейки достигает 2, Вася запускает змейку в тренировочный опасный лабиринт; цель змейки— выбраться оттуда как можно быстрее, если она выживает, то по достижении длины 3 обучение повторяется в том же лабиринте, и так пока змейка не станет совершенно длинной (длины 18) либо не погибнет.
Лабиринт можно представить себе как прямоугольник ширины
W и длины
H,
каждая клетка которого — либо препятствие 'X', либо свободное место '.'. Лабиринт окружён непроходимыми камнями '*', за исключением одной клетки '#', смежной входу в лабиринт, который расположен на границе лабиринта. Вот, например, простой лабиринт длины 4 и ширины 3:
***#**
*.X.X*
*.X..*
*....*
******
Змейка длины
L представляет собой последовательность из
L клеток. Каждая клетка последовательности смежна с соседними клетками по стороне. Все клетки в последовательности различны. Змейка может ползти относительно текущего направления движения в трёх направлениях: прямо, налево или направо. Змейка ползёт одновременно всем телом, и каждая клетка, кроме первой, занимает место предыдущей. Вот примеры допустимых движений змейки:
321. -> .321
-
321 -> .32
... ..1
-
12 -> 23
.3 1.
-
12 -> 23
43 14
Змейка за каждую единицу времени проползает ровно одну клетку,
если же ей некуда ползти, то она погибает.
Исходные данные
В первой строке находятся размеры лабиринта H и W (1 ≤ H ≤ 300, 1 ≤ W ≤ 30). Во второй строке находятся координаты входа h0 и w0. Причем либо h0 = 1, либо h0 = H, либо w0 = 1, либо w0 = W. Далее следуют H строк по W символов — построчное описание лабиринта, где 'X' обозначает препятствие, а '.' свободную клетку. Отсчёт времени начинается с 0; начальное положение змейки: голова в точке (h0,w0), остальная часть тела снаружи. Отсчёт времени заканчивается, когда голова змейки вновь окажется в клетке (h0,w0). И ещё, лабиринт хоть и тренировочный, но ни одна змейка длины 18 не может выбраться оттуда живой.
Результат
Выход должен содержать 16 строчек, где i-я строчка представляет собой лучшее время, за которое змейка длины i+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
| 10
10
10
22
22
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
|
Автор задачи: Дмитрий Иванков
Источник задачи: Petrozavodsk summer training camp, August 2005.