问题 N: 小挖的 X 献身

问题 N: 小挖的 X 献身

时间限制: 1 Sec  内存限制: 256 MB
提交: 59  解决: 42
[提交][状态][讨论版][命题人:]

题目描述


给定一张 n\times nn×n 的 0101 方阵,请计算其中 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 行每行一个长度为 nn 的 0101 串,描述了一个 0101 矩阵。

输出

共 11 行,表示 X 的数目。

样例输入

5
10001
01010
00100
01011
00011

样例输出

2

提示


对于 20\%20% 的数据,1\leq n\leq 31n3



对于 40\%40% 的数据,1\leq n\leq 101n10



对于 70\%70% 的数据,1\leq n\leq 501n50



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

[提交][状态]