2024 上海市大学生编程新锐挑战赛

J. Count S
PDF 题面可用
你可以在这里下载。

单点时限: 1.0 sec

内存限制: 512 MB

给定一张 $n \times n$ 的网格图,部分点为黑色,其余点为白色,请你统计其中 $S$ 图的数量。

大小为 $k$ 的 $S$ 图定义为:
1. 由 $5$ 条长度为 $k$ 的线段组成 $(k \geqslant 1)$
2. $5$ 条线段首尾相连,且只覆盖黑色的点(注意是线段上的所有格点均为黑色,而不仅仅是端点)
3. 形如 “S”,即 $5$ 条线段的端点坐标如下:

$\quad (a,b),(a, b- k)$
$\quad (a,b-k),(a+k, b- k)$
$\quad (a+k,b-k),(a+k, b)$
$\quad (a+k,b),(a+2k, b)$
$\quad (a+2k,b),(a+2k, b-k)$

注意,我们认为网格图从上到下编号依次为 $1$ 到 $n$,从左到右编号依次为 $1$ 到 $n$。

例如,下图包含一张大小为 $5$ 的 $S$ 图。

注意,下图不包含 $S$ 图。

输入格式

输入的第一行包含一个整数 $n \ (1 \leqslant n \leqslant 50)$,表示网格图的大小。

接下来 $n$ 行,每行一个长度为 $n$ 的字符串 $s_i \ (1 \leqslant i \leqslant n)$。
用 $s_{i, j}$ 表示 $s_i$ 的第 $j \ (1 \leqslant j \leqslant n)$ 个字符 $(s_{i,j} \in \lbrace$ o, x $\rbrace)$,$s_{i,j} = $o 表示网格图中从上到下第 $i$ 行、从左到右第 $j$ 列的点为白色,$s_{i, j} = $x 表示点为黑色。

输出格式

输出一行一个整数,表示网格图中 $S$ 图的数量。

样例

Input
3
xxo
xxo
xxo
Output
1
Input
4
ooxx
ooxx
ooxx
ooxx
Output
2
Input
3
xxx
xox
xxx
Output
0