레인 부츠
시간 제한1초메모리 제한1024 MB
각 8×8 격자에서 S에서 E까지 갈 때 밟아야 하는 진흙 웅덩이('M')의 최소 개수를 구합니다.
문제
여러분은 새 장화가 마음에 들어서 최대한 깨끗하게 유지하고 싶습니다. 위성 데이터로 근처 지역을 진흙이 있는 곳과 없는 곳으로 나눈 격자를 만들었습니다. 목적지에 도착할 때까지 밟아야 하는 진흙 웅덩이의 최소 개수를 구하는 프로그램을 작성하세요.
기호는 다음과 같습니다.
- 'M': 진흙 웅덩이
- '-': 진흙 없음
- 'S': 시작 지점 (진흙 없음)
- 'E': 도착 지점 (진흙 없음)
입력
입력의 개수는 정해져 있지 않습니다. 각 입력은 근처 지역을 나타내는 8×8 격자입니다. 입력과 입력 사이는 '-' 하나만 적힌 한 줄로 구분됩니다.
출력
각 입력에 대해 목적지에 도달할 때까지 밟아야 하는 진흙 웅덩이의 최소 개수를 출력하세요.