한 비밀 연구소는 \(R \times C\) 격자 모양의 방들로 이루어져 있다. 각 칸은 다음 중 하나이다.

• . : 자유롭게 지나갈 수 있는 복도
• # : 벽 (지나갈 수 없음)
• D : 잠긴 문. 이 칸에 들어가려면 카드키를 1번 사용해야 한다.
• S : 출발 위치
• E : 목표 위치

요원은 상하좌우로 인접한 칸으로 한 칸씩 이동할 수 있다. 복도(.)나 출발/목표 칸에 들어갈 때는 비용이 들지 않지만, 잠긴 문(D) 칸에 들어갈 때마다 카드키를 1번 써야 한다. 출발 위치 \(S\) 에서 목표 위치 \(E\) 까지 도달하는 데 필요한 카드키 사용 횟수의 최솟값을 구하여라.

도달이 불가능하면 \(-1\) 을 출력한다.

\(1 \le R, C \le 1{,}000\), 격자에는 정확히 하나의 \(S\) 와 하나의 \(E\) 가 있다.

첫째 줄에 격자의 행 수 \(R\) 과 열 수 \(C\) 가 주어진다. (\(1 \le R, C \le 1{,}000\))

다음 \(R\) 개의 줄에 격자가 주어진다. 각 줄은 ., #, D, S, E 로 이루어진 길이 \(C\) 의 문자열이다. \(S\) 와 \(E\) 는 정확히 하나씩 존재한다.

카드키 사용 횟수의 최솟값을 출력한다. 도달이 불가능하면 \(-1\) 을 출력한다.

riseoj 작성

출처 Original