/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
N\times N のマス目が与えられます。 上から i 行目 (1\leq i\leq N)、左から j 列目 (1\leq j\leq N) のマスをマス (i,j) と呼ぶことにします。
それぞれのマスは空きマスか壁マスのどちらかです。
マスの状態は N 個の文字列 S _ 1,S _ 2,\ldots,S _ N で与えられ、S _ i の j 文字目が . のときマス (i,j) は空きマス、# のときマス (i,j) は壁マスです。
ここで、マス目の一番外側のマス、すなわちマス (1,j),(i,1),(N,j),(i,N)\ (1\leq i\leq N,1\leq j\leq N) はすべて壁マスであることが保証されます。
高橋くんは、ある空きマス (x,y) で上下左右のいずれかの方向を向いているところから始めて次の操作を繰り返したところ、（始点を含む）ある時点でマス (2,2) を訪れました。
- 現在向いている方向に隣り合っているマスが空きマスならば、向いている方向を変えないまま、そのマスに移動する。 そうでなければ、同じマスにとどまり、時計回りに 90 度回転する。
たとえば、高橋くんがマス (3,5) で上を向いている状態で操作を行った場合、マス (2,5) が空きマスならばマス (2,5) に移動し、壁マスならば右を向きます。
高橋くんが操作を始めたマスとしてありえる空きマスがいくつあるか求めてください。
制約
- 3\leq N\leq1000
- N は整数
- S _ i は
.および#からなる長さ N の文字列 (1\leq i\leq N) - S _ 1,S _ N は
#のみからなる文字列 - S _ i の 1 文字目と N 文字目はどちらも
#と等しい (1\leq i\leq N) - S _ 2 の 2 文字目は
.と等しい
入力
入力は以下の形式で標準入力から与えられる。
N S _ 1 S _ 2 \vdots S _ N
出力
答えを出力せよ。
入力例 1
6 ###### #....# #....# #.#..# #...## ######
出力例 1
13
与えられたマス目は以下のようになっています。
14 個の空きマスのうち、マス (4,5) 以外の 13 マスについては、適切な向きで操作を始めることでマス (2,2) を訪れることができます。
たとえば、マス (4,4) で下を向いている状態から操作を始めると、高橋くんは以下のように移動してマス (2,2) を訪れます。
入力例 2
4 #### #.## ##.# ####
出力例 2
1
入力例 3
13 ############# #.....####..# #....#....#.# #...#......## #...#..###.## #...#.#..#.## #...#.#..#.## #...#.#....## #...#..#.##.# #....#......# #.....##.##.# #...........# #############
出力例 3
85
Problem Statement
There is an N\times N grid. The cell in the i-th row (1\leq i\leq N) from the top and j-th column (1\leq j\leq N) from the left is called cell (i,j).
Each cell is either an empty cell or a wall cell.
The state of the grid is represented by N strings S _ 1,S _ 2,\ldots, and S _ N:
if the j-th character of S _ i is ., then cell (i,j) is an empty cell; if it is #, it is a wall cell.
Here, the outermost cells, namely cells (1,j),(i,1),(N,j),(i,N)\ (1\leq i\leq N,1\leq j\leq N), are guaranteed to be wall cells.
Initially located at an empty cell (x,y) facing one of the four directions (up, down, left, and right), Takahashi repeated the following move. During his tour, he visited cell (2,2) at some point (including the initial position):
- If the adjacent cell in his facing direction is an empty cell, then advance to that cell without changing his direction. Otherwise, rotate clockwise by 90 degrees while staying at the same cell.
For example, if he makes the move when he is facing up at cell (3,5), he will advance to cell (2, 5) if cell (2,5) is an empty cell, and turn right if it is a wall cell.
How many cells are there where he can have been initially located?
Constraints
- 3\leq N\leq1000
- N is an integer.
- S _ i is a string of length N consisting of
.and#(1\leq i\leq N). - S _ 1 and S _ N are strings consisting solely of
#. - The 1-st and N-th characters of S _ i both equal
#(1\leq i\leq N). - The 2-nd character of S _ 2 equals
..
Input
The input is given from Standard Input in the following format:
N S _ 1 S _ 2 \vdots S _ N
Output
Print the answer.
Sample Input 1
6 ###### #....# #....# #.#..# #...## ######
Sample Output 1
13
The given grid looks like this.
Among the 14 empty cells, if he starts at one of the 13 cells except for cell (4,5), he can always visit cell (2,2) if he initially faces in an appropriate direction.
For example, if he starts at cell (4,4) facing down, he will visit cell (2,2) as follows.
Sample Input 2
4 #### #.## ##.# ####
Sample Output 2
1
Sample Input 3
13 ############# #.....####..# #....#....#.# #...#......## #...#..###.## #...#.#..#.## #...#.#..#.## #...#.#....## #...#..#.##.# #....#......# #.....##.##.# #...........# #############
Sample Output 3
85