Description
Capybara-san loves high-quality meat (vegan-friendly) imported from the USA!
He wants to find meat in the maze.
- '.' is a path
- '#' is a wall
- 'S' is his starting point
- 'M' is the meat
If Capybara-san is at position (x, y), then he can walk to:
- (x + 1, y)
- (x - 1, y)
- (x, y + 1)
- (x, y - 1)
All 4 movements are counted by 1 step, and also valid if that position is not a wall
How many steps does he need to walk?
The maze is made as:
- For every position (a, b) and (c, d), where (a, b) ≠ (c, d), there is only 1 path solution from (a, b) to (c, d)
Input
The first input is X, and Y (X is row, Y is column) of the map
The next input is X * Y map,
5 <= X, Y <= 300
It's guaranteed that there is always S, M, and a path between that 2 points
Output
Output the steps, following with a newline