帮“绝艺”数气

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

            前不久 ,腾讯开发的人工智能“绝艺”在世界围棋电圣战中力压群雄,夺得冠军,成为除 alphago 以外的世界最强的围棋 AI。但是,据绝艺内部人员所说,绝艺的弱项是数气。数气是围棋当中一项简单而又重要的任务,你能帮助绝艺完成这项任务吗?

            再次之前,玄黄需要为大家普及一下围棋气的基本知识,棋子落入棋盘上后,便有了气,气是棋子赖以生存的源泉,当棋子的气都被对面棋子占领时,那它就要离开棋盘了。那么棋子的气是什么呢?就是棋子在棋盘上相邻的交叉点。见下图:

 

3868

 

中间的那一个棋子有四个相邻的交叉点,因此它有四口气,上边的那一个棋子由于棋盘边界的限制,所以只有三口气,右上角的棋子只有两口气,左下角的两个棋子连在了一起,气是共用的,共有六口气,右下角三个棋子有 7 口气。(你再不会数的话玄黄就疯了!)

 

围棋的棋盘太大,我们把问题简单化,现在有一个 n*n 的棋盘,我们把棋盘上的空位用 0 表示,把棋盘上有黑棋的位置用 1 表示,问题就是这一块黑棋的气是多少。

Input

输入数据有多组。每组数据第一行输入一个整数 n (1 < n < 20),接下来有 n 行,输入 0 表示棋盘上空位,用棋子的位置,输入保证有且仅有一块棋,且这块棋至少有 1 口气,即至少有一个 1 和一个 0 且所有的 1 在棋盘上都是连在一起的,详情见示例输入。

Output

对于每组输入,输出一个整数,表示这块棋有多少口气。

Sample Input

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

Sample Output

4
2
5
1

Hint

Source

玄黄