W키가 빠진 성원이

면접 대비

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

요약

N x N 보드에서 W 키를 제외한 일곱 개의 키로 F에 도달할 수 있는 빈 시작 칸의 개수를 구합니다.

난이도: 쉬움10점 중 3점
유형: BFS, 그래프, 행렬
정답자: 아직 제출이 없습니다

문제

성원이는 게임을 너무 열심히 한 나머지 키보드의 W키가 빠져버렸다. 그럼에도 게임이 하고 싶었던 성원이는 W키 없이도 할 수 있는 게임을 찾아 나섰고, 한 게임을 찾았다. 보통의 게임은 WASD로 캐릭터를 움직이지만, 이 게임은 Q, W, E, A, D, Z, X, C 키로 8방향 이동이 가능하다. 성원이는 W키를 누를 수 없으므로 나머지 7개 키로만 캐릭터를 움직인다. 각 키를 눌렀을 때의 이동은 다음과 같다.

Q: 왼쪽 위 대각선으로 1칸 이동
W: 위쪽으로 1칸 이동
E: 오른쪽 위 대각선으로 1칸 이동
A: 왼쪽으로 1칸 이동
D: 오른쪽으로 1칸 이동
Z: 오른쪽 아래 대각선으로 1칸 이동
X: 아래쪽으로 1칸 이동
C: 왼쪽 아래 대각선으로 1칸 이동

목표는 $N\times N$ 게임판에서 8방향 키(성원이는 7방향)를 사용해 목적지에 도달하는 것이다. 게임판에서 빈 공간은 ., 캐릭터가 지나갈 수 없는 벽은 #, 목적지는 F로 표시한다. 게임을 시작하기 전에 플레이어는 빈 공간 중 원하는 곳에 캐릭터를 둘 수 있다. 벽이나 목적지 위에는 둘 수 없다. 목적지는 항상 하나만 있다.

#.#
.#.
.#F

위 게임판에서 캐릭터를 맨 왼쪽 아래에 두지만 않으면 성원이는 목적지에 도달할 수 있다. 성원이가 목적지에 도달할 수 있는 시작 지점의 개수를 구하라.

입력

첫 줄에 정수 $N$ 이 주어진다. $(1 \le N \le 2000)$ 둘째 줄부터 $N$ 개의 줄에 걸쳐 게임판이 주어진다.

출력

첫 줄에 성원이가 목적지에 도달할 수 있는 시작 지점의 개수를 출력한다.

예제2

예제 1
입력
```
3
#.#
.#.
.#F
```
예상 출력
```
3
```

예제 2

입력

7
###F###
##.#.##
#..#..#
##.#..#
.#.###.
...##..
.#.#...

예상 출력