시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 38 10 7 35.000%

문제

$4k$×$4k$의 크기인 미로가 있다. 이 미로의 최상단 왼쪽을 $(1, 1)$, 최하단 오른쪽을 $(4k, 4k)$로 하자.

$4×i≤ y < 4×(i+1)$, $4×j ≤ x < 4×(j+1)$ $(1 ≤ i,j ≤ k)$를 만족하는 $(y, x)$ 들을 하나의 구역으로 구분되어 있다. 아래 그림은 $k$가 2인 미로를 4×4 크기로 구역을 나누고 각 구역마다 다른 색상으로 칠한 것이다. $(y, x)$에 써져있는 숫자들은 구역의 번호이다.

예를 들어, $(2, 3)$와 $(3, 4)$은 둘다 구역 1이므로 같은 구역에 속하고 $(2, 3)$와 $(3, 5)$는 각각 구역 1, 구역 2이므로 다른 구역이다.

미로를 탈출 할때 아래와 같은 순서로 진행된다.

  1. 상하좌우로 이동하거나 가만히 있는다. 단, 이동할 곳에 벽이 있거나 미로를 벗어나는 곳이면 이동하지 못한다.
  2. 1번이 끝나고 현재 서 있는 위치 $(y, x)$가 포함된 구역이 시계방향으로 90도 회전한다.
  3. 현재 서 있는 부분을 포함하는 구역을 제외한 나머지 구역들은 맨 처음에 주어진 방향으로 다시 돌아간다.
  4. 미로를 탈출할때까지 1번 ~ 3번을 반복한다.

미로는 시작 부분인 'S', 이동할 수 있는 곳 '.', 벽 '#', 탈출할 수 있는 곳 'E'로 구성되어 있다. 'S'에서 출발하여 'E'로 갈때 최소 이동거리를 구해보자.

입력

첫 번째 줄에 $k$가 들어온다.

다음 $4k$ 줄에는 $4k$개의 문자로 미로의 정보가 붙어서 주어진다.

출력

'S'에서 출발하여 'E'로 갈때 최소 이동거리를 출력한다. 만약, 탈출을 하지 못하는 경우엔 -1을 출력한다.

제한

  • $1 ≤ k ≤ 125$

예제 입력 1

1
S.#E
.#..
.#.#
...#

예제 출력 1

9

예제 입력 2

1
S.#E
.#..
#..#
...#

예제 출력 2

-1

예제 입력 3

2
#S#.#.##
#...E#.#
#.##.##.
#....###
#.#..##.
#......#
#..##..#
########

예제 출력 3

2
  1. 가만히 서있는다.
  2. 이동한다.

출처