题目描述

Always known for being quite tech-savy, Farmer John is testing out his new automated drone-mounted cow locator camera, which supposedly can take a picture of his field and automatically figure out the location of cows. Unfortunately, the camera does not include a very good algorithm for finding cows, so FJ needs your help developing a better one.

The overhead image of his farm taken by the camera is described by an $N \times N$ grid of characters, each in the range $A \ldots Z$, representing one of 26 possible colors. Farmer John figures the best way to define a potential cow location (PCL) is as follows: A PCL is a rectangular sub-grid (possibly the entire image) with sides parallel to the image sides, not contained within any other PCL (so no smaller subset of a PCL is also a PCL). Furthermore, a PCL must satisfy the following property: focusing on just the contents of the rectangle and ignoring the rest of the image, exactly two colors must be present, one forming a contiguous region and one forming two or more contiguous regions.

AAAAA
ABABA
AAABB

For example, a rectangle with contents would constitute a PCL, since the A's form a single contiguous region and the B's form more than one contiguous region. The interpretation is a cow of color A with spots of color B.

A region is "contiguous" if you can traverse the entire region by moving repeatedly from one cell in the region to another cell in the region taking steps up, down, left, or right.

Given the image returned by FJ's camera, please count the number of PCLs.

输入格式

The first line of input contains $N$, the size of the grid ($1 \leq N \leq 20$).

The next $N$ lines describe the image, each consisting of $N$ characters.

输出格式

Print a count of the number of PCLs in the image.

题目大意

题目描述

Farmer John 一直以精通技术而闻名，他正在测试他的新型无人机搭载的奶牛定位相机。这款相机据说可以拍摄他的田地并自动确定奶牛的位置。不幸的是，相机的算法并不擅长寻找奶牛，因此 Farmer John 需要你的帮助来开发一个更好的算法。

相机拍摄的农场俯视图由一个 $N \times N$ 的字符网格描述，每个字符在 $A \ldots Z$ 范围内，代表 26 种可能的颜色之一。Farmer John 认为，定义潜在奶牛位置（PCL）的最佳方式如下：一个 PCL 是一个矩形子网格（可能是整个图像），其边与图像的边平行，并且不包含在任何其他 PCL 中（因此 PCL 的较小子集不能也是 PCL）。此外，PCL 必须满足以下属性：仅关注矩形内的内容并忽略图像的其余部分，必须恰好存在两种颜色，其中一种颜色形成一个连续区域，另一种颜色形成两个或更多连续区域。

例如，一个矩形的内容如下：

AAAAA  
ABABA  
AAABB  

这将构成一个 PCL，因为 A 形成一个连续区域，而 B 形成多个连续区域。解释为一只颜色为 A 的奶牛带有颜色为 B 的斑点。

一个区域是“连续的”，如果可以通过向上、向下、向左或向右移动，从一个区域中的单元格反复移动到另一个区域中的单元格来遍历整个区域。

给定 Farmer John 的相机返回的图像，请计算 PCL 的数量。

输入格式

输入的第一行包含 $N$，表示网格的大小（$1 \leq N \leq 20$）。

接下来的 $N$ 行描述图像，每行包含 $N$ 个字符。

输出格式

输出图像中 PCL 的数量。

说明/提示

在这个例子中，两个 PCL 分别是内容如下的矩形：

ABB  
BBB  
AAB  
ABB

和

BC  
BC  
BB  
BC  

4
ABBC
BBBC
AABB
ABBC

2

提示

In this example, the two PCLs are the rectangles with contents

ABB
BBB
AAB
ABB

and

BC
BC
BB
BC