Де Бессі?

Фермер Джон, який завжди відрізнявся хорошими технічними навичками, тестує свою нову автоматичну камеру для пошуку корів, встановлену на дроні. Передбачається, що камера може сфотографувати його поле і автоматично визначити місцезнаходження корів. На жаль, камера не має достатньо хорошого алгоритму для виявлення корів, тому Фермеру Джону потрібна ваша допомога у розробці кращого алгоритму.

Зображення ферми, отримане камерою зверху, подано у вигляді сітки n \times n, що складається із символів у діапазоні $A..Z$, кожен з яких позначає один із $26$ можливих кольорів. Фермер Джон вирішив, що найкращим способом визначити потенційне місцезнаходження корови (PCL) є наступний: PCL — це прямокутна підматриця (можливо, така, що збігається з усім зображенням) зі сторонами, паралельними сторонам зображення, яка не містить всередині себе повністю жодного іншого PCL. Крім того, PCL повинен задовольняти наступну умову: якщо розглядати лише вміст прямокутника і ігнорувати решту зображення, у ньому повинні бути присутні рівно два кольори, причому один колір утворює одну зв'язну область, а інший — дві або більше зв'язних областей.

Наприклад, прямокутник із наступним вмістом

AAAAA
ABABA
AAABB

є PCL, оскільки символи $A$ утворюють одну зв'язну область, а символи $B$ утворюють більше однієї зв'язної області. Це можна інтерпретувати як корову кольору $A$ з плямами кольору $B$.

Область вважається «зв'язною», якщо з будь-якої її клітинки можна дістатися до будь-якої іншої клітинки цієї області, багаторазово переміщуючись вгору, вниз, вліво або вправо і залишаючись при цьому всередині області.

Отримавши зображення, зроблене камерою Фермера Джона, визначте кількість PCL.