축제장에 \(R \times C\) 격자 모양으로 부스가 배치되어 있다. 각 칸은 자유롭게 지나갈 수 있는 통로 . 이거나 막힌 부스 # 이다. 길잡이 로봇은 출발 칸 S 에서 도착 칸 E 까지 이동한다.

로봇은 상하좌우로 한 칸씩 움직일 수 있는데, 직진(이전과 같은 방향으로 이동) 할 때는 비용이 들지 않지만 방향을 바꿀 때마다 비용이 1 든다. 단, 출발 직후 첫 번째 이동은 어느 방향으로 가도 비용이 들지 않는다(아직 진행 방향이 정해지지 않았으므로).

\(S\) 에서 \(E\) 까지 가는 데 필요한 방향 전환 횟수의 최솟값을 구하여라. 도달이 불가능하면 \(-1\) 을 출력한다.

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

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

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

방향 전환 횟수의 최솟값을 출력한다. 도달이 불가능하면 \(-1\) 을 출력한다.

riseoj 작성

출처 Original