← 返回题目列表

AtCoder · past21_j

J. 右转

中文机器翻译题面 查看原题

问题陈述

有一个 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: 如果 j- 第一个字符 S _ i is .,然后是单元格 (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 是仅包含以下内容的字符串 #.
  • 的 1-st 和 N第一个字符 S _ i 两者相等 # (1\leq i\leq N).
  • 的 2-nd 字符 S _ 2 等于 ..

输入

输入由标准输入按以下格式给出:

N
S _ 1
S _ 2
\vdots
S _ N

输出

打印答案。


示例输入 1

6
######
#....#
#....#
#.#..#
#...##
######

示例输出 1

13

给定的网格如下所示。

其中 14 空单元格,如果他从其中之一开始 13 细胞(细胞除外) (4,5),他可以随时访问单元格 (2,2) 如果他最初面向适当的方向。

例如,如果他从单元格开始 (4,4) 面朝下,他将访问牢房 (2,2) 如下。


示例输入 2

4
####
#.##
##.#
####

示例输出 2

1

示例输入 3

13
#############
#.....####..#
#....#....#.#
#...#......##
#...#..###.##
#...#.#..#.##
#...#.#..#.##
#...#.#....##
#...#..#.##.#
#....#......#
#.....##.##.#
#...........#
#############

示例输出 3

85