회전 미로 탐색

면접 대비

시간 제한1초메모리 제한1024 MB

요약

4k×4k 미로에서 매시간 이동하거나 제자리에 머문 뒤, 현재 칸이 속한 4×4 구역을 시계 방향으로 90도 돌릴 때 출구까지 가는 최소 시간을 구합니다.

난이도: 보통10점 중 5점
유형: BFS, 그래프, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

미로의 크기는 $4k$ × $4k$ 이다. 가장 왼쪽 위 칸을 $(1, 1)$ , 가장 오른쪽 아래 칸을 $(4k, 4k)$ 라고 하자.

$\{(y, x) \mid 4 \times i < y \le 4 \times (i+1), 4 \times j < x \le 4 \times (j+1), (0 \le i, j < k)\}$ 를 만족하는 영역이 하나의 구역으로 구분된다. 쉽게 말해, 4×4 크기의 영역이 하나의 구역이다. 아래 그림은 $k$ 가 2인 미로를 4×4 크기의 구역으로 나누고, 구역마다 다른 색으로 칠한 것이다. $(y, x)$ 에 적힌 숫자는 구역의 번호이다.

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

미로를 탈출할 때까지 매 시간마다 다음 순서로 진행된다.

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

미로는 시작 칸 'S', 이동할 수 있는 칸 '.', 벽 '#', 탈출할 수 있는 칸 'E'로 구성된다. 'S'에서 출발하여 'E'에 도착하는 최소 이동 시간을 구하라.

입력

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

출력

'S'에서 출발하여 'E'로 갈 때의 최소 이동 시간을 출력한다. 탈출할 수 없으면 -1을 출력한다.

제한

$1 \le k \le 125$

예제3

예제 1
입력
```
1
S.#E
.#..
.#.#
...#
```
예상 출력
```
9
```
예제 2
입력
```
1
S.#E
.#..
#..#
...#
```
예상 출력
```
-1
```

예제 3

입력

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

예상 출력