시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 272 | 74 | 54 | 38.028% |
$4k$×$4k$의 크기인 미로가 있다. 이 미로의 최상단 왼쪽을 $(1, 1)$, 최하단 오른쪽을 $(4k, 4k)$로 하자.
$\{(y, x) | 4×i < y ≤ 4×(i+1), 4×j < x ≤ 4×(j+1), (0 ≤ i, j < k)\}$ 를 만족하는 영역이 하나의 구역으로 구분되어 있다. 쉽게 말해, 4x4 크기를 하나의 구역으로 본다는 것이다. 아래 그림은 $k$가 2인 미로를 4×4 크기로 구역을 나누고 각 구역마다 다른 색상으로 칠한 것이다. $(y, x)$에 써져있는 숫자들은 구역의 번호이다.
예를 들어, $(2, 3)$와 $(3, 4)$은 둘다 구역 1이므로 같은 구역에 속하고 $(2, 3)$와 $(3, 5)$는 각각 구역 1, 구역 2이므로 다른 구역이다.
미로를 탈출할 때까지 매 시간마다 아래와 같은 순서대로 진행된다.
미로는 시작 부분인 'S'
, 이동할 수 있는 곳 '.'
, 벽 '#'
, 탈출할 수 있는 곳 'E'
로 구성되어 있다. 'S'
에서 출발하여 'E'
로 갈때 최소 이동시간을 구해보자.
첫 번째 줄에 $k$가 들어온다.
다음 $4k$ 줄에는 $4k$개의 문자로 미로의 정보가 주어진다.
'S'
에서 출발하여 'E'
로 갈때 최소 이동시간을 출력한다. 만약, 탈출을 하지 못하는 경우엔 -1을 출력한다.
1 S.#E .#.. .#.# ...#
9
1 S.#E .#.. #..# ...#
-1
2 #S#.#.## #...E#.# #.##.##. #....### #.#..##. #......# #..##..# ########
2