#D11205. Acrophobia
Acrophobia
Acrophobia
C: Acrophobia
Yayoi Takasugi is a super-selling idol. There is one thing she is not good at. It's a high place ... She is extremely afraid of heights. This time, due to the producer's inadequacy, she decided to take on the following challenges on a variety show.
This location will be held in a room in a ninja mansion. The floor of this room is lined with square tiles, and some tiles have fallen out to form holes. If you fall through this hole, you will find yourself in a pond a few meters below. Yayoi's challenge is to start from the designated place in this room, collect all the scrolls placed in the room, and bring them to the goal point.
Yayoi can move in the room according to the following rules.
- When moving from one tile to the next, you can only move to the top, bottom, left, and right tiles.
- If it is not close to the hole, it will take 1 second to move to the next tile.
- If you get close to the hole, Yayoi will be scared and it will take time to move as shown in Fig. C-1. For example, it takes 3 seconds to move from [2] [2] to [1] [2] as shown by the arrow in the figure.
- If there are multiple holes nearby, you will be afraid of the nearest hole.
- The time it takes to take a scroll can be assumed to be 0.
Yayoi wants to finish this challenge as soon as possible. Your job is to help Yayoi write a program that asks for the shortest time to complete this challenge.
Input
The floor information of the ninja mansion is given.
First, W and H, which represent the size of the room, are entered on the first line, separated by spaces (2 <= W, H <= 100). A W character string is input to each of the following H lines. There are the following types of characters that represent floor information.
*'.': Walkable floor
- '#' : hole *'S': Where Yayoi stands at the start *'G': Yayoi's place to reach *'M': Where the scroll is located
'S',' G'and'M' are walking floors. There is exactly one'S'and one'G'in the room, respectively. You may pass the goal without all the scrolls. There are a minimum of 1'M'and a maximum of 5'M'in the room.
Output
Collect all the scrolls and output the shortest time to reach the goal from the start on one line. You can always assume that the input data has such a route. Output a line break at the end of the line.
Sample Input 1
3 4 S.M ... ... M.G
Sample Output 1
9
Sample Input 2
4 4 S..M .... ... # ..G
Sample Output 2
18
Sample Input 3
11 7 M ......... M ........... ... #. S. # ... ........... ... #. G. # ... ........... M ......... M
Sample Output 3
62
Example
Input
3 4 S.M ... ... M.G
Output
9
inputFormat
Input
The floor information of the ninja mansion is given.
First, W and H, which represent the size of the room, are entered on the first line, separated by spaces (2 <= W, H <= 100). A W character string is input to each of the following H lines. There are the following types of characters that represent floor information.
*'.': Walkable floor
- '#' : hole *'S': Where Yayoi stands at the start *'G': Yayoi's place to reach *'M': Where the scroll is located
'S',' G'and'M' are walking floors. There is exactly one'S'and one'G'in the room, respectively. You may pass the goal without all the scrolls. There are a minimum of 1'M'and a maximum of 5'M'in the room.
outputFormat
Output
Collect all the scrolls and output the shortest time to reach the goal from the start on one line. You can always assume that the input data has such a route. Output a line break at the end of the line.
Sample Input 1
3 4 S.M ... ... M.G
Sample Output 1
9
Sample Input 2
4 4 S..M .... ... # ..G
Sample Output 2
18
Sample Input 3
11 7 M ......... M ........... ... #. S. # ... ........... ... #. G. # ... ........... M ......... M
Sample Output 3
62
Example
Input
3 4 S.M ... ... M.G
Output
9
样例
3 4
S.M
...
...
M.G9