23563번 - 벽 타기

루시우는 높이가 $H$이고 너비가 $W$인 맵의 시작점에서 끝점까지 이동하려고 한다.

• 맵은 $H$개의 행과 $W$개의 열로 이루어진 격자판 모양이다. 각 칸은 벽 또는 빈칸이다.
• 루시우는 상, 하, 좌, 우 방향 인접한 칸으로 한 칸씩 이동할 수 있다. 벽으로는 이동할 수 없다.
• 루시우가 한 칸을 이동하는 데에는 1초가 걸린다.
• 하지만 루시우가 벽을 타고 이동하면 순식간에 (0초의 시간에) 상, 하, 좌, 우 방향 인접한 칸으로 이동할 수 있다.
  • 어떤 빈칸의 상하좌우 중 하나가 벽이면 이 칸은 벽에 인접한 칸이라고 한다.
  • 벽에 인접한 칸에서 벽에 인접한 칸으로 이동하면 벽을 타고 이동한다고 말한다.

루시우가 맵의 시작점에서 끝점까지 이동하는 데 걸리는 최소 시간을 구하여라.

첫째 줄에는 $H$와 $W$가 공백을 사이에 두고 주어진다. 맵은 $H$개의 행과 $W$개의 열로 이루어진 격자판 모양이다.

둘째 줄부터, $H$개의 줄에 걸쳐서 맵의 모습을 나타내는 $W$개의 문자가 주어진다.

• #는 벽을 뜻한다.
• .는 빈칸을 뜻한다.
• S는 맵의 시작점을 뜻한다. 시작점은 빈칸이다.
• E는 맵의 끝점을 뜻한다. 끝점은 빈칸이다.

루시우가 맵의 시작점에서 끝점까지 이동하는 데 걸리는 최소 시간을 출력하라.

• $1 \le H \le 500$
• $1 \le W \le 500$
• 격자판의 모든 칸들은 ., #, S, E 중 하나의 문자로 주어진다.
• 시작점 S와 끝점 E는 각각 하나씩만 주어진다.
• 맵의 가장 바깥 (1번째 열, $W$번째 열, 1번째 행, $H$번째 행) 칸들은 모두 벽이다.
• 시작점에서 끝점까지 이동할 수 없는 경우는 주어지지 않는다.