问题 3853 --Bessie在哪里

3853: Bessie在哪里

题目描述

  

       众所周知,农场主John正在测试他最新研制的全自动奶牛定位照相机,这个照相机据称可以对他的牧场进行拍照,并自动计算出奶牛们的位置。

       不幸的是,这个照相机没有一个很好的算法来识别奶牛,所以John希望你能帮助他开发一个这样的算法。

       照相机拍的牧场的俯视图可以用N×N的字母矩阵表示,字母范围为A..Z,可以表示26种颜色。John认为,一个潜在奶牛位置(下文简称PCL)需要满足以下条件:

a、 PCL是一个子矩阵(有可能是整张牧场俯视图),它的边是和牧场俯视图的边相平行。

b、 一个PCL中不能包含其他更小的PCL。即如果出现包含的情况,只记一个PCL

c、  PCL必须满足一下条件:在子矩阵上,一共有且只有2种颜色,其中一种颜色要求是连续的,另一种要求被分割成2个以上区域。

       比如说,下面这个颜色矩阵

AAAAA

ABABA

AAABB

       这里有一个PCL。其中A是连续区域,B是被分割成2个及以上的区域。可以理解为一头主体颜色是A,斑点颜色是B的奶牛。

       所为一个区域是“连续的”,就是通过一步一步上、下、左、右的移动可以贯彻这整个区域。

       给出这牧场俯视图,请你计算出一共有多少个PCL

输入

    第一行:n表示输入矩阵的长宽(1<=N<=20)

    接下来N行,每行N个字符,表示这个牧场的俯视图。

输出

   输出这个图的PCL的个数

样例输入输出

输入#1 复制
4
ABBC
BBBC
AABB
ABBC
输出#1 复制
2

提示

序号 标题 作者 发表时间 费用 订购数 操作