Змійка#4971

Змійка

3 секунди

64 мегабайти

Дуже складна

Відомо, що змійкам нелегко виживати в лабіринтах. Навіть якщо змійка одна в лабіринті, вона може загинути, врізавшись у стіну або у свій хвіст. Вася, який прагне перемогти в конкурсі змійок, вирішив навчити свою змійку уникати небезпечних ділянок лабіринту. Небезпека таких "підлабіринтів" полягає в тому, що шанси змійки вибратися звідти живою невеликі, і чим довша змійка, тим менші ці шанси. Вася тренує змійку так: коли її довжина досягає $2$ , він запускає її в тренувальний небезпечний лабіринт. Мета змійки — вибратися звідти якомога швидше. Якщо вона виживає, то при досягненні довжини $3$ навчання повторюється в тому ж лабіринті, і так далі, поки змійка не стане дуже довгою (довжини $18$ ) або не загине.

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

Змійка довжини $L$ складається з послідовності з $L$ клітинок. Кожна клітинка послідовності суміжна з сусідніми клітинками по стороні. Усі клітинки в послідовності різні. Змійка може рухатися відносно поточного напрямку в трьох напрямках: прямо, наліво або направо. Змійка рухається всім тілом одночасно, і кожна клітинка, крім першої, займає місце попередньої. Ось приклади допустимих рухів змійки:

$321. \to .321$ 321. \to .321

$321 \to .32$ 321 \to .32

$... ..1$

$12 \to 23$ 12 \to 23

$.3 1.$

$12 \to 23$ 12 \to 23

$4314$

Змійка за кожну одиницю часу проповзає рівно одну клітинку. Якщо їй нікуди повзти, вона гине.

Вхідні дані

У першому рядку подано розміри лабіринту $H$ і $W$ ( $1 \leq H \leq 300$ 1 \le H \le 300, $1 \leq W \leq 30$ 1 \le W \le 30). У другому рядку подано координати входу $h_{0}$ h_0 і $w_{0}$ w_0. Причому або $h_{0} = 1$ h_0 = 1, або $h_{0} = H$ h_0 = H, або $w_{0} = 1$ w_0 = 1, або $w_{0} = W$ w_0 = W. Далі йдуть $H$ рядків по $W$ символів — построчний опис лабіринту, де ' $X$ ' позначає перешкоду, а ' $.$ ' — вільну клітинку. Відлік часу починається з $0$ ; початкове положення змійки: голова в точці $(h_{0}, w_{0})$ (h_0, w_0), решта частини тіла зовні. Відлік часу закінчується, коли голова змійки знову опиниться в клітинці $(h_{0}, w_{0})$ (h_0, w_0). І ще, лабіринт хоч і тренувальний, але жодна змійка довжини $18$ не може вибратися звідти живою.

Вихідні дані

Вихід повинен містити $16$ рядків, де $i$ -й рядок представляє найкращий час, за який змійка довжини $i + 1$ i+1 може вибратися з лабіринту, або $- 1$ , якщо вона неминуче гине.

Приклади

Приклад 1