Description
Researchers found that giant panda don't move much, and when they do, it is usually for finding meals. Surprisingly, researchers have measured that pandas only expend low amount of energy per day, and due to the inadequate nutrients provided by their daily meal, they have to slow things down to avoid their energy from expending.
Now, assume that you are the panda keeper, in order to decrease the energy consumption of the panda, your boss ask you to design the shortest path from panda's shelter to meal area. However, there are some obstacles in the panda farm, you also need to bypass these obstacles.
The farm is a m x n matrix, and it consists five symbols:
'.' is the road that panda can walk through.
'^' and 'o' is the tree and rock that panda can not walk through.
'S' is the the panda's shelter.
'M' is the meal area.
Your goal is to find the length of the shortest path from panda's shelter S to their meal area M.
Note that you can only move left, right, up, and down (diagonal move is not acceptable) !
For example,
if the 5 x 5 farm looks like:
. . . . S
. o o ^ ^
. . . . o
^ o ^ . o
M . . . o
(There is a space in front of each charactor!)
the length of the shortest path is 14 (including M):
. . . . S
. o o ^ ^
. . . . o
^ o ^ . o
M . . . o
Input
The first line contains two integers m, n, which is length and width of the farm (1 ≤ m, n ≤ 1000)
The next m lines contains n characters (including '.', '^', 'o', 'S', 'M' ) which builts the aerial view of the farm
Output
The length of the shortest path in the farm (it is guaranteed that there is always a path from pandas' shelter S to the meal area M).
Note that the shortest path must include M, and you need to print a newline character ('\n') at the end.