Description
一向以技术娴熟著称的农场主约翰正在测试他新的自动无人机奶牛定位摄像头,据称该摄像头可以拍下他的田地,并自动找出奶牛的位置。不幸的是,相机没有一个很好的算法来寻找奶牛,所以需要你的帮助,开发一个更好的。
农场的俯瞰图被定义为一个n * n的字符矩阵。矩阵由大写字母A到Z组成,每个字母表示一种可行的颜色。农夫John发现一个可能是奶牛的位置(以下简称PCL)的最好定义如下:
一个PCL是一个矩阵(可能是整张图),矩阵的边与图像的边缘平行,且不能被其他PCL所包含(因此PCL内部不可能有PCL)更多的,一个PCL必须满足以下特性:
1、矩阵有且只能有2种颜色构成。
2、这两种颜色一种构成一个连通块,另一种形成两个或两个以上的连通块。
举个例子:
AAAAA
ABABA
AAABB
这个矩阵就是一个PCL,其中颜色A构成一个连通块,B构成两个连通块,描述了一只可能以A为底色,B为花纹的奶牛。
在这里连通块被定义为:从其中的任何一个点,你能仅通过上下左右移动,到达另外任何一个点(即上下左右相邻)
给定农场的照片,请你计算图中有几个PCL。
Input
第一行输入一个整数N
接下来N行,,每行N个字符。
HINT
2
在这个例子中,这两个PCL分别是:
ABB
BBB
AAB
ABB
and
BC
BC
BB
BC