Description
Capybara-san really likes meat (vegan-friendly), so now he wants to gather a lot of meats and saves all of them in his tent.
He start from his tent (letter 'S') and want to gather all meat in the maze (letter 'M')
He can only bring one meat per trip and he wants to take all the meat to his tent.
- '.' is a path
- '#' is a wall
- 'S' is his tent
- '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
What is the smallest step does Capybara-san need to take to gather all the meat back to his tent?
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) without overlapping path!
Sample IO Explanation:
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 <= 500
It's guaranteed that there is always S, M, and a path between that 2 points
Output
Output the steps, following with a newline