ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1391. Змейка

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
Всем известно, что нелегко живётся змейкам в лабиринтах. Даже если змейка одна в лабиринте, она может погибнуть, врезавшись в стену или в свой хвост. Некто Вася, претендент на победу в конкурсе змеек, решил научить свою змейку выбираться из опасных частей лабиринта. Опасность таких «подлабиринтов» в том, что шансы змейки выбраться оттуда живой малы, и, конечно, чем длиннее змейка, тем ниже шансы. Вася проводит обучение змейки так: в юном возрасте, когда длина змейки достигает 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.