Super Mario
Super Mario is very unhappy. Evil Crocodile has kidnapped princess. But! Super Mario is planning an attack. There are spies at the castle. He gave him a map of the castle and eliminate all obstacles except the walls and alarm. Super Mario from each field on the map can move up, down, left and right. Wishes as soon as possible to reach the princess and back as he would not have turned on the alarm. Tell him how much time may be minimal doc and princesses, and get rid of the starting point for each if the shift to a second and can not pass through walls.
InputThe first line of Natural numbers R and S, the number of rows and columns in the castle. R,S <=50 .The next R lines is with a sign, this is a map of the castle, which is our hero Mario comes from the spies. Sign of M indicates a field in which Super Mario moves and ends (just one on the map). Sign of p is a field where there is a princess (just one on the map). Character '. " denotes an empty field, and the character '#' wall.
OutputOne number that stands for how many seconds Super Mario can get to and back princess or -1 if you can get to princesses.
Input
Output
5 5
M#P..
.###.
.#...
.#.##
.....Output
28Input
Output
5 5
.#P..
.###.
.#...
.####
M....Output
-1Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.