Where is the Bessie.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python, VB

Siempre conocido por ser amante de la tecnología, el Granjero Juan está probando su nueva cámara ubicadora de vacas montada en un dron, la cual supuestamente puede tomar una fotografía de su campo y encontrar automáticamente la ubicación de vacas. Desafortunadamente, la cámara no incluye un buen algoritmo para encontrar vacas, por lo tanto GJ necesita su ayuda desarrollando uno mejor.

La imagen de la granja tomada por la cámara está descrita por una cuadrícula \(N×N\) de caracteres, cada uno en el rango A...Z, representando uno de 26 colores posibles. El Granjero Juan piensa que la mejor manera de definir una ubicación potencial de vaca (PCL) es la siguiente: Una PCL es una subcuadrícula rectangular (posiblemente toda la imagen) con lados paralelos a los lados de la imagen, no contenida en otra PCl (entonces ningún subconjunto más pequeño de una PCL es también una PCL). Aún más una PCL debe satisfacer la siguiente propiedad: enfocándose en los contenidos en el rectángulo e ignorando el resto de la imagen, deben estar presentes exactamente dos colores, uno formando una región continúa y uno formando dos o más regiones contiguas.

Por ejemplo, un rectángulo con contenidos

AAAAA
ABABA
AAABB

podría constituir una PCL, desde que las A's forman una sola región contigua y las B's forman más de una región contigua. La interpretación es una vaca de color A con manchas de color B.

Una región es "contigua" si usted puede recorrer toda la región moviéndose repetidamente de una celda a otra en la región tomando pasos arriba, abajo, derecha, o izquierda.

Dada la imagen devuelta por la cámara de GJ, por favor cuente el número de PCLs.

Entrada

La primera línea de la entrada contiene N, el tamaño de la cuadrícula (1 \leq N \leq 20). Las siguientes N líneas describen la imagen, cada una consistiendo de N caracteres.

Salida

Imprima una cuenta del número de PCLs en la imagen.

Ejemplo de Entrada

4
ABBC
BBBC
AABB
ABBC

Ejemplo de Salida

2

En este ejemplo, las dos PCLs son los rectángulos con contenidos

Explicación

ABB
BBB 
AAB
ABB

y

BC
BC
BB
BC

Comments

There are no comments at the moment.