Rain Boots

You love your new rain boots and want to keep them as clean as possible. Using satellite data you have gridded the area nearby as either muddy or not muddy. Write a program that will determine the fewest number of muddy puddles you must walk through to reach a destination.

Key:

• ‘M’ – Muddy Puddle
• ‘-’ – No Mud
• ‘S’ – Start (No Mud)
• ‘E’ – End (No Mud)

There will be an unknown number of inputs. Each input will contain an 8 by 8 grid that represents the area nearby. There will be a single line containing a single ‘-‘ separating each input.

For each input, display the fewest number of muddy puddles you must step through to reach the destination.