Responsive image

问题 3169 --气

3169: 气

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

题目描述

围棋中有“气”的说法
一个棋子在棋盘上,与它直线紧邻的空点(不包含斜线)是这个棋子的“气”。棋子直线紧邻的点上,如果有同色棋子存在,则它们便相互连接成一个不可分割的整体。它们的气也应一并计算。棋子直线紧邻的点上,如果有异色棋子存在,这口气就不复存在。

上图中:1.紫色号棋子因左边和下边是棋盘边缘,所以仅有上方和右方的两口气。2.红色号棋子四周无障碍,四个方向都有气,所以有四口气。3.绿色号棋子相同颜色且相邻故而看作一个整体,其四周一共有6口气。4.橙色棋子下方被绿色棋子阻挡,左方右方上方有三口气,绿色棋子同理;
现在有一个n*n大小的棋盘,其中仅有两种颜色的棋子(黑色为:"1",白色为"2",空位为"0",不包含引号),要求你算出其中黑色棋子气的总和并且输出。
(当两部分棋子共用一口气时仅算一次)

输入描述

第一行输入一个n代表棋盘边长
接下来的n行输入棋盘内容

输出描述

一个数字代表黑色棋子气的总和

样例输入

5
1 0 0 1 0
0 0 0 2 0
0 2 1 0 0
0 0 1 1 0
0 1 0 0 0

样例输出

11

提示

测试用例:n<10

来源

[提交][状态]
ACM算法攻关部