Problem Description
Squirrely has lost his lifetime collection of acorns in an unfortunate geyser accident and now he needs your help! Roll the animals around and get Squirrely to the Acorn, but beware! Not all animals are fluffy as they appear to be. Start from your home forest, and continue through the harsh weather of the snow, the scary swamp and the vast wild west! In your journey you will encounter great dangers, but don’t worry! You and Squirrely will be a great team.
Get the Nut is a very cute game as mentioned above. Now Squirrely is in a forest, which can be divided into 6 rows and 8 columns, 48 grids in total. Squirrely wants to get the nut in another grid. However, it is much more difficult than you can image because the forest is full of danger. There are two kinds of other animal in the forest: Mouse and Pig. Pigs are very vicious, they will kill and eat any other animal (except Pigs, of course) in the adjacent grids. Here “adjacent” means two grids share a common edge. Once any other animal enter grids adjacent to a Pig, it will stop and be eaten. Once an animal is adjacent to the nut, it will stop and eat the nut. So if Squirrely is eaten by a Pig or the nut is eaten by a Pig or a Mouse, the game is over and you fail. At the beginning of the game, each animal occupies one grid. For each step, you can choose one animal to roll in either up, down, left or right direction, the animal will keep rolling until it reach the border of the forest or hit a tree or an animal. Your task is to calculate the minimal number of steps should be made that Squirrely can get the nut.
Input
There are multiple test cases. Please process till EOF.
Each test case gives the map of the forest, which has 6 rows and 8 columns. Each grid of the map is one of the following six characters:
- '.' - the empty area which every animal can stay or go through
- '#' - the tree which is an obstacle
- 'S' - the Squirrely
- 'M' - a Mouse
- 'P' - a Pig
- 'N' - the nut which the Squirrely want to get
You should notice that there is one blank line before every test case. You may assume that there is one and only one nut in the forest and the number of animals in the forest will not exceed 5, and the input guarantees that there are at most 32 empty grids(including the original grids occupied by animals) in the map.
Output
For each test case, output a positive integer indicating the desired answer. You may assume that there is always exists a solution to get the nut, and the minimal number of steps should be made will not exceed 30.
Sample Input
#......N
###.####
###M####
###.####
###.####
###S####
########
###.####
##.....#
#S.M.P.N
########
########
########
S...M.##
####M.##
####M.##
###P..##
####N.##
P.....M#
...##..#
P..##..#
.###...#
..N#...#
.###..S#
Sample Output
4
4
5
15
