问题6945--奶牛位置

6945: 奶牛位置

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MiB

题目描述

【题目描述】

农民约翰一直以精通技术而闻名,他正在测试他新的自动无人机奶牛定位相机,据说它可以拍摄他的田地,并自动找出奶牛的位置。不幸的是,相机没有一个很好的算法来寻找奶牛,所以FJ需要你的帮助开发一个更好的算法。

摄像机拍摄的农场头顶图像由N×N网格字符描述,每个字符的范围为AZ,代表26种可能的颜色之一。农民约翰认为定义潜在奶牛位置(PCL)的最佳方法如下:PCL是一个矩形子网格(可能是整个图像),其边与图像边平行,不包含在任何其他PCL(因此PCL中没有更小的子集也是PCL)。此外,PCL必须满足以下属性:只关注矩形的内容而忽略图像的其余部分,必须恰好有两种颜色,一种形成一个连续的区域,另一种形成两个或多个连续的区域。

例如,一个包含内容的矩形

AAAAA

ABABA

AAABB

将构成一个PCL,因为A形成了一个连续的区域,而B形成多个连续区域。这种解释是一头带有B色斑点的a色奶牛。

如果可以通过从区域中的一个单元格重复移动到区域中的另一个单元格,并采取向上、向下、向左或向右的步骤来遍历整个区域,则区域是“连续的”。

 

根据FJ相机返回的图像,请统计PCL的数量。

【输入格式】(where.in):

第一行输入一个整数N(1N20),即网格的大小。接下来的N行描述图像,每一行由N个字符组成。

【输出格式】(where.out):

输出图像中PCL数量的计数。

【样例输入】:

4

ABBC

BBBC

AABB

ABBC

样例输出:

2

【样例说明】

在本例中,两个PCL是包含内容的矩形

ABB

BBB

AAB

ABB


BC

BC

BB

BC

 

来源/分类