Rotating maze zone search

Interview

Time limit1sMemory limit1024 MB

Summary

Find the fewest hours to reach the exit in a 4k by 4k maze where each hour you move or stay, then the 4x4 zone you stand in rotates 90 degrees clockwise.

Level: Medium5 of 10
Topics: BFS, Graph, Simulation
Solved: No attempts yet

Problem

The maze is $4k$ × $4k$ in size. Let the top-left cell be $(1, 1)$ and the bottom-right cell be $(4k, 4k)$ .

The region $\{(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)\}$ forms one zone. Put simply, each 4×4 block is a zone. The figure below shows a maze with $k = 2$ split into 4×4 zones, each colored differently. The number written at $(y, x)$ is the zone number.

For example, $(2, 3)$ and $(3, 4)$ are both in zone 1, so they are in the same zone. $(2, 3)$ and $(3, 5)$ are in zones 1 and 2, so they are in different zones.

Each hour, the following steps happen in order until the maze is escaped.

Move up, down, left, or right, or stay in place. A move is blocked if the target cell is a wall or lies outside the maze.
After step 1, the zone containing the current position $(y, x)$ rotates 90 degrees clockwise.
Every zone except the one containing the current position returns to its initial orientation.
If the current position is an exit, you escape the maze.

The maze consists of a start cell 'S', open cells '.', walls '#', and exit cells 'E'. Find the minimum time to go from 'S' to 'E'.

Input

The first line contains $k$ . Each of the next $4k$ lines contains $4k$ characters describing the maze.

Output

Print the minimum time to go from 'S' to 'E'. If escape is impossible, print -1.

Constraints

$1 \le k \le 125$

Examples3

Example 1
Input
```
1
S.#E
.#..
.#.#
...#
```
Expected output
```
9
```
Example 2
Input
```
1
S.#E
.#..
#..#
...#
```
Expected output
```
-1
```

Example 3

Input

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

Expected output