Rain Boots

Time limit1sMemory limit1024 MB

Summary

Find the fewest muddy puddles ('M') you must step on to get from S to E in each 8x8 grid of the nearby area.

Level: Easy3 of 10
Topics: Shortest path, BFS, Matrix
Solved: No attempts yet

Problem

You love your new rain boots and want to keep them as clean as possible. Using satellite data, you have gridded the nearby area as either muddy or not muddy. Write a program that determines 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)

Input

There are an unknown number of inputs. Each input is an 8×8 grid that represents the nearby area. A single line containing one '-' separates consecutive inputs.

Output

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

Examples1

Example 1

Input

S-------
-M------
--M-----
---M----
----M-MM
-----M--
-----M--
-----ME-
-
SM------
MM------
--------
MMMMMMMM
--------
MMM-----
MEM-----
-----ME-
-
-------M
-MMMMM-M
-MS--M-M
-MMM-M-M
-----M-M
MMMMMM-M
-------M
EMMMMMMM
-
-M-MEM-M
M-M-M-M-
-M-M-M-M
M-M-M-M-
-M-M-M-M
M-M-M-M-
SM-M-M-M
M-M-M-M-

Expected output