#P8546. 小挖的 X 献身

小挖的 X 献身

题目描述

给定一张 n×nn\times n0101 方阵,请计算其中 X 的数目。

X 定义为用 11 填充且形状为 X 的联通块。具体的,X 由左向斜线 \ 和右向斜线 / 构成,且需要保证左向斜线和右向斜线长度相等,而且 X 是中心对称图形,斜线长度大于 1。

例如:

101
010
101

有一个斜线长度为 33 的 X。

1001
0110
0110
1001

则有两个斜线长度分别为 2,42,4 的 X。

10001
01010
00100
01010
00001

仅有一个斜线长度为 33 的 X 。

输入格式

11 行,共一个正整数 nn

接下来 nn 行每行一个长度为 nn0101 串,描述了一个 0101 矩阵。

输出格式

11 行,一个非负整数,表示 X 的数目。

5
10001
01010
00100
01011
00011
2

提示

对于 20%20\% 的数据,1n31\leq n\leq 3

对于 40%40\% 的数据,1n101\leq n\leq 10

对于 70%70\% 的数据,1n501\leq n\leq 50

对于 100%100\% 的数据,1n1001\leq n\leq 100