时间限制:1000ms  空间限制:256MB

题目描述

输入一个 $n×n$ 的黑白图像（1表示黑色，0表示白色），任务是统计其中八连块的个数。如果两个黑格子有公共边或者公共顶点，就说它们属于同一个八连块。如下图所示的图形有3个八连块。

输入格式

第 1 行输入一个正整数 $n（n≤700）$，此后输入 $n$ 行，每行是由 $n$ 个 0 或 1 组成的字符串。

输出格式

输出八连块的个数。

样例

输入#1

6
100100
001010
000000
110000
111000
010100

输出#1

3

数据范围/约定

对于 100% 的测试数据满足：$1≤N≤700$。

注意数据范围，本题使用深度优先搜索有 RE 的风险，请谨慎使用深度优先搜索！