29703번 - 펭귄의 하루

$1$ × $1$ 크기의 정사각형 칸으로 각각 나누어져 있는 $N$ × $M$의 행렬로 표현되는 펭귄 마을이 있다. 펭귄 마을의 정보는 문자 'S', 'H', 'E', 'D', 'F'로 나타난다. E는 천적이 없어 펭귄이 이동해도 괜찮은 안전 구역을 나타내며, D는 펭귄의 천적인 바다표범이 살고 있어 펭귄이 이동할 수 없는 위험 구역을 나타낸다. 그리고 F는 펭귄이 먹이를 구할 수 있는 물고기 서식지를 의미한다.

펭귄 마을에서 펭귄은 위험 구역이 아닌 곳을 상하좌우로 이동한다. 단, 펭귄은 멸종위기 동물이기 때문에 멸종 위기 동물 보호 구역인 펭귄 마을 밖으로는 이동할 수 없다.

펭귄이 현재 위치에서 출발하여 물고기 서식지 중 최소한 한 곳을 들러 사냥을 마치고 집으로 돌아가려 한다. 펭귄이 사냥하는 데 걸리는 시간은 고려하지 않으며 출발 지점에서 먼저 물고기들이 서식하는 구역을 들르지 않았더라도 펭귄이 사는 집을 지나갈 수 있다. 또한, 물고기들이 서식하는 구역을 들른 후에 펭귄이 출발한 지역을 거쳐 펭귄의 집으로 돌아갈 수 있다. 펭귄 마을에서 한 칸을 이동하는 데 $1$초가 걸린다고 할 때, 물고기를 사냥해 최대한 빠르게 펭귄의 집에 도달하는 데 걸리는 시간을 구해보자.

첫째 줄에는 펭귄 마을의 세로 길이 $N$($ 1 \leq N \leq 1\,000$)과 가로 길이 $M$($ 1 \leq M \leq 1\,000$)이 주어진다.

둘째 줄부터 $N$개의 줄에 펭귄 마을의 위치 정보를 나타내는 길이 $M$의 문자열이 주어진다. 이 문자열은 S, H, E, D, F로 이루어져 있고, 아래와 같은 의미를 가진다.

• S: 펭귄의 현재 위치
• H: 펭귄의 집
• E: 안전 구역
• D: 위험 구역
• F: 물고기 서식지

펭귄의 현재 위치와 펭귄의 집은 공간에 $1$개만 있으며 물고기 서식지는 공간에 $1$개 이상 $1\,000$개 이하로 존재한다.

펭귄이 물고기 서식지를 들러 집에 도착할 때 걸리는 최소 시간을 출력한다. 만약, 펭귄이 물고기 서식지를 들러 집에 도착할 수 없다면 $-1$을 출력한다.