시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 43 11 11 37.931%

문제

Amy는 Farmer John의 며느리이다. Farmer John은 호주 청정우인 Amy를 탐탁치 않게 생각하고 있었다. 그러던 어느 날, Amy가 끓인 건초 수프를 맛 본 Farmer John은 극대노 했다.

FJ: [ Amy야, 국이 짜다! ]
Amy: [ 그건 물인데요. ]
FJ: [ 물도 짜다! ]
Amy: [ 먼 곳을 항해하는 배가 풍파를 만나지 않고 조용히만 갈 수는 없다. 풍파는 언제나 전진하는 자의 벗이다. 차라리 고난 속에 인생의 기쁨이 있다. ]

수도꼭지에 맺힌 물방울이 씽크대를 향해 떨어지는 그 순간, Farmer John과 Amy가 위치한 주방의 평면도가 주어진다. 주방은 $N \times N$ 크기의 정사각형 격자로 표현된다.

  1. $(r, c)$의 상하좌우를 인접한 네 격자인 $(r+1, c), (r-1, c), (r, c+1), (r, c-1)$라고 하자.
  2. 최초에, 씽크대가 있는 격자에서 소리가 발생한다. 최초의 소리가 발생한지 1초가 지나면, 최초의 소리는 상하좌우로 퍼지고 소멸한다.
  3. 씽크대를 제외한 격자 $(r, c)$의 소리는 1초가 지나면 직전에 머무른 격자를 제외한, 인접한 세 격자로 퍼져 나간다. 예를 들어 소리가 $(r-1, c)$에서 $(r, c)$로 왔다면, $(r+1, c), (r, c+1), (r, c-1)$로 소리가 퍼져 나간다.
  4. 격자 $(r, c)$에, 동시에, 서로 다른 2개 이상의 격자로부터 소리가 도달하면, 소리는 인접한 세 격자로 퍼지지 않고 관성에 의해 움직인다. 직전 격자들의 위치를 각각 $(r-dr_{i}, c-dc_{i})$라고 하자. 1초 뒤부터 $(r, c)$의 소리는 $(\sum_{i} dr_{i}, \sum_{i} dc_{i})$의 속도로 이동한다. $|\sum_{i} dr_{i}|, |\sum_{i} dc_{i}|$가 각각 2 이상의 자연수일 수 있음에 유의하라. 단, $(\sum_{i} dr_{i}, \sum_{i} dc_{i})$가 모두 0이면 소리는 소멸한다.
  5. (4)에 의해 이동한 소리는 다른 소리와 부딪히거나 소멸하기 전까지 계속 같은 방향과 속력으로만 이동한다. 인접한 2개 이상의 격자로 퍼지지 않는다.
  6. 격자 밖 또는 장애물로는 소리가 퍼져 나가지 않고 소멸한다.
  7. 소리의 이동은 순간이동으로 취급되어 장애물을 뛰어 넘을 수 있고, 도착지를 제외한 경로 내의 빈 격자는 방문하지 않은 것으로 간주한다. 경로 내에 다른 소리들이 있더라도 서로 영향 받지 않는다.

폭 풍 전 야. 여러분은 물방울이 씽크대에 떨어지는 소리가 장애물을 제외한 주방의 모든 빈 격자에 도달할 수 있는지 판정해야 한다.

입력

첫 번째 줄에 격자의 크기 $N$이 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 $N \times N$ 크기의 주방의 평면도가 주어진다.

출력

소리가 장애물을 제외한 모든 격자를 한 번 이상 방문하는 데 필요한 최소 시간(초)을 출력한다. 불가능한 경우 -1을 출력한다.

제한

  • $1 \le N \le 11$
  • 모든 격자 $A_{r,c}$ ($1 \le r,c \le N$)는 씽크대 'S' 또는 빈 격자 '.' 또는 장애물 '@'로 구성되어 있다.
  • 'S'는 반드시 하나 주어진다.

예제 입력 1

1
S

예제 출력 1

0

예제 입력 2

7
@@@@@@@
@..S..@
@.@@@.@
@.....@
@@@.@@@
@.....@
@@@@@@@

예제 출력 2

-1

예제 입력 3

7
@@@@@@@
@..S..@
@.@@@.@
@.....@
@@.@@@@
@.....@
@@@@@@@

예제 출력 3

10

예제 입력 4

3
.@.
@@.
..S

예제 출력 4

-1