Where's Bessie?

题目描述

Farmer John 一直以很懂科技而闻名，他正在测试自己新买的自动化无人机载奶牛定位相机。据说它可以拍摄农田的俯视图，并自动推断奶牛的位置。不幸的是，这台相机寻找奶牛的算法不太好，所以 FJ 需要你帮忙开发一个更好的算法。

相机拍下的农场俯视图由一个 $N \times N$ 的字符网格描述，每个字符都在 $A \ldots Z$ 范围内，表示 26 种可能颜色之一。Farmer John 认为定义“潜在奶牛位置”(PCL) 的最佳方式如下：PCL 是一个矩形子网格（可能是整张图），其边与图像边平行，并且不被包含在任何其他 PCL 内（因此，一个 PCL 的任何更小子集都不会也是 PCL）。

此外，一个 PCL 必须满足如下性质：只关注该矩形内部的内容并忽略图像其余部分时，矩形内恰好出现两种颜色，其中一种颜色形成一个连通区域，另一种颜色形成两个或更多个连通区域。

例如，内容为 AAAAA ABABA AAABB 的矩形就构成一个 PCL，因为 A 形成一个单一连通区域，而 B 形成不止一个连通区域。其含义是：一头颜色为 A 的奶牛，带有颜色为 B 的斑点。

如果你可以通过在区域内反复从一个格子移动到另一个格子，并且每一步只能向上、下、左或右移动，从而遍历整个区域，那么该区域称为“连通”。

给定 FJ 相机返回的图像，请统计 PCL 的数量。

输入格式

第一行输入包含 $N$，表示网格大小（$1 \leq N \leq 20$）。 接下来的 $N$ 行描述图像，每行由 $N$ 个字符组成。

输出格式

输出图像中 PCL 的数量。

4
ABBC
BBBC
AABB
ABBC

2

提示

在该示例中，两个 PCL 分别是内容为 ABB BBB AAB ABB 以及 BC BC BB BC 的矩形。

题目来源：Brian Dean

标签: USACO|2017|Silver

来源

USACO|2017|Silver