Castle
НОИ 2010, Кръг 3
Time Limit: 0.1s, Memory Limit: 64MiB
Ели и Крис бягаха ли бягаха от дракона, гледайки назад как той ги гони. Изведнъж, докато бягаха, се блъснаха в нещо зелено, люспесто и ядосано – а именно – неговия гръб. Ели стана, изтупа се, и каза: "Ех, как ги мразя тези не-евклидови замъци!"

Малко след като се събуди, все още ярко помнеща как заедно с нейната приятелка Крис спасяваха Принцове в далечни царства от пазещите ги митични същества, тя реши да изготви по-продуктивен план за спасяването им в бъдеще. По-точно как, по дадена карта на замъка - къде се намира тя, принцовете и изхода - да изчисли минималното време, за което може от своята позиция да мине през всеки от тях и да стигне до изхода, движейки се само нагоре, надолу, наляво или надясно.

Замъкът ще е зададен под формата на матрица от символи с N реда и M колони. Всеки символ може да бъде 'Е', означаващ къде се намира Ели в началото, 'X', означаващ къде се намира изходът, 'P', означаващ, че на текущата клетка има принц, '.' означаващ празен коридор или '#', означаващ стена. Не бива да забравяте, че тя се намира в не-евклидов замък, тоест слизайки под най-долния ред на замъка тя се появява в най-горния в същата колона (и обратно); също така прекрачвайки най-дясното поле на замъка тя се появява в най-лявото на същия ред (и обратно). Разбира се, тя може да прави това само ако никое от двете полета не е стена, както и по принцип – тя не може да минава през стени (все още). Погледнете примерния вход за пояснение.

Считаме, че времето за преминаване от една клетка в друга е една минута (включително при прехвърляне между най-горния и най-долния ред или най-лявата и най-дясната колона). Освобождаването на принц отнема пренебрежимо малко време.
Вход
На първия ред на стандартния вход ще бъдат зададени размерите на замъка – целите числа N и M. На всеки от следващите N реда ще има по M символа, които могат да бъдат '.', '#', 'E', 'X' или 'P'.
Изход
На единствен ред на стандартния изход изведете едно цяло число – броя минути, нужни на Ели да освободи всички принцове и да стигне до изхода. Ако това е невъзможно изпечатайте -1.
Ограничения
  • 1 ≤ N, M ≤ 50
  • Броят на принцовете ще бъде по-малък или равен на 5.
Примерен Вход Примерен Изход
5 11 #....#..... ...E....X.. .######P##. .########.. .P.#....P.. 14
3 4 E.#. X##. #..P 4
В първия пример замъкът има 5 реда и 11 колони. Ели се намира на втория ред, четвърта колона, изходът на 2-ри ред, 9-та колона, а трите принца са на третия и петия ред. Най-краткият път на Ели от началната й позиция (2, 4) е да отиде веднъж наляво, два пъти нагоре, преминавайки от най-горния ред в най-долния, после още веднъж наляво за да стигне до първия принц. Оттам нататък тя може да мръдне още два пъти наляво, минавайки от най-лявата в най-дясната колона, още два пъти наляво за да стигне до втория принц. След като освободи и него, веднъж надолу би я пратило на най-горния ред в позиция (1, 9). Оттам нататък ходовете й са веднъж надолу, веднъж наляво, веднъж надолу, веднъж нагоре, и веднъж надясно. Забележете, че Ели спокойно може да преминава през полето на изхода колкото си иска пъти докато освобождава принцовете. Общият брой ходове, които тя трябва да направи е 14. Има и други оптимални маршрути, но те дават същото сумарно време. Забележете също, че Ели не може да отиде два пъти нагоре от началната си позиция, тъй като ще се удари в стена (независимо, че е на най-долния ред).
Мрън!