시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB114373140.260%

문제

루시우는 높이가 $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$번째 행) 칸들은 모두 벽이다.
  • 시작점에서 끝점까지 이동할 수 없는 경우는 주어지지 않는다.

예제 입력 1

5 5
#####
#..E#
#.S.#
#...#
#####

예제 출력 1

1

출발하자마자 오른쪽으로 한 칸 이동하고, 위로 한 칸 벽을 타고 이동하면 총 1의 시간이 소요된다.

예제 입력 2

10 10
##########
#........#
#...#....#
#........#
#.E....S.#
#........#
#........#
##.......#
#........#
##########

예제 출력 2

2

출발하자마자 오른쪽으로 한 칸 이동하면, 벽을 타고 순식간에 끝점 왼쪽 칸으로 이동할 수 있다.

출처

University > 제주대학교 > 2021 하반기 취업 알고리즘 집중특강 및 해커톤 대회 E번