카페의 일회용 통행 카드

문제

한 카페는 여러 방과 복도를 격자 모양의 평면도로 관리한다. 평면도는 R행 C열이며, 각 칸은 직원이 설 수 있는 공간 하나 또는 벽을 나타낸다. 직원은 출발 칸 S에서 준비를 마친 음료를 들고 인계 칸 T로 이동해야 한다. 음료를 들고 있으므로 한 번 이동할 때 상하좌우로 인접한 칸 중 하나로만 이동할 수 있다. 대각선으로 이동하거나 평면도 바깥으로 나갈 수는 없다. 평면도에서 마침표는 일반 통로이고 X는 벽이다. 벽에는 어떤 경우에도 들어갈 수 없다. 문자 D는 잠금문이 설치된 공간을 나타낸다. 출발 칸과 인계 칸은 일반 통로처럼 드나들 수 있으며, 이 두 칸 자체에는 잠금문이 없다. 서로 다른 잠금문 칸은 각각 별개의 문으로 취급한다. 직원은 잠금문 칸에 들어갈 때 사용할 수 있는 일회용 통행 카드 한 장을 가지고 있다. 일반 통로에서 잠금문 칸으로 이동하거나 다른 잠금문 칸에서 잠금문 칸으로 이동하면, 도착하는 칸에 들어가기 위해 카드 한 장이 필요하다. 사용한 카드는 즉시 사라진다. 잠금문은 열린 상태로 유지되지 않으므로 이전에 방문한 잠금문 칸에 다시 들어갈 때도 카드가 필요하다. 잠금문 칸에서 일반 통로로 나갈 때는 카드가 필요하지 않다. 모든 인접 칸으로의 이동에는 같은 시간이 걸린다. 카드 사용 자체는 별도의 이동으로 세지 않으며, 카드를 전혀 사용하지 않고 도착해도 된다. 직원이 S에서 T까지 이동하는 데 필요한 최소 이동 횟수를 구한다. 같은 최소 횟수의 경로가 여러 개여도 경로는 출력하지 않는다. 카드 사용 규칙을 지키면서 도착할 수 있는 경로가 없다면 -1을 출력한다.

입력

첫째 줄에 정수 R과 C가 주어진다. 1 ≤ R, C ≤ 300이며 2 ≤ R × C ≤ 90,000이다.
다음 R개의 줄에 길이가 C인 평면도가 주어진다. 각 문자는 '.', 'X', 'D', 'S', 'T' 중 하나다. S와 T는 각각 정확히 하나씩 주어지며 서로 다른 칸이다.

출력

최소 이동 횟수를 정수 하나로 출력한다. 도착할 수 없다면 -1을 출력한다.

3 4
S.DT
.XX.
....

3

3 3
SXT
XXX
...

-1

2 4
SDDT
....

5

출처: Devin.KR 자체 제작