#1413. 国家宝藏

国家宝藏

国家宝藏

题目描述

某日他居然进入了传说中的国家宝藏。这个区域是个n×nn \times n的矩形方块。

每个方块可能放置的是宝物或者是不可翻越的障碍。当某个方块放的是宝物时,如果其上下左右的某个方块放置的亦是宝物时,则两个方块则被认为是互相连通的。

联通的宝藏可以一次性取走。

输入格式

第一行一个数字nn,代表矩形方块的长。

接下来的nnnn列,代表宝物的分布,其中00代表宝物,11代表障碍。

输出格式

输出取宝藏的次数。

数据范围与提示

  • 对于30%30\%的数据,1n101 \leq n \leq 10
  • 对于100%100\%的数据,1n10001 \leq n \leq 1000

样例

3
0 0 0
1 1 1
0 0 0
2
3
0 1 1
0 0 0
1 1 0
1