White Horses
ПрАнКА 2010
Time Limit: 0.1s, Memory Limit: 64MiB
Ели цял живот търси принца на бял кон, за да го спаси от ламята и да заживеят happily ever after. Даже понякога си мисли, че го е намерила, но само след няколко дни се убеждава в обратното. Интересен факт е, че след това никой никога не го вижда отново. Какво точно се случва с принцовете остава мистерия. Всъщност някои от тях бяха достатъчно смели да я попитат, при което тя шеговито отговаряше "Ако ти кажа ще трябва да те убия." Или поне всички си мислеха, че се шегува.

Освен да се занимава с разни принцове, Елеонора има и друга работа – затова тя гледа набързо да се справи с потенциалните кандидати за деня, след което да си прави нейните неща. Тя се чуди за колко най-малко време може всеки от принцовете-кандидати да стигне до нея, тя да го "изпробва" и, най-вероятно, той да изчезне. Под "изпробва" разбирайте дуелиране, шах партия или игра на Heroes 3. Всъщност можете да си мислите и това, което първоначално ви хрумна – за целите на задачата това няма значение.

Кралството на Ели ще е зададено като матрица от символи с N реда и M колони. Всеки символ би могъл да бъде '.', означаващ проходима местност, '#', означаващ непроходима местност, 'E', означаващ замъка на Ели, или 'P', което пък показва принц. Принцовете могат да се придвижват в някое от съседните 4 полета, стига те да не са непроходими, като това им отнема по един час.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и M. Следващите N реда ще съдържат по M символа, описващи кралството.
Изход
На единствен ред на стандартния изход изведете едно цяло число – сбора на времената, нужни на принцовете за да стигнат до Ели. Ако дори един от тях не може да го направи, вместо това изпечатайте -1.
Ограничения
  • 2 ≤ N, M ≤ 200
Примерен Вход Примерен Изход
5 9 P###..P.. ...#E#.#P .#..P.... .P...#.PP .P#.P..#. 42
1 5 .EP#P -1
Във втория пример единият от принцовете не може да достигне до Ели, затова печатаме -1.
Мрън!