Informatica Online Judge

  배시는 어디에? [1996 / 07CC]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 5   Total Tried : 4


The Champion of this Problem (C++) : gs16106 - 0ms / 1666byte
My Best Submission (C++) : N/A

[USACO]

Background

하이테크 농부 존은 드론에 장착해 사용할 수 있는 젖소 위치 추적 카메라를 테스트하고 있다. 위치 추적 카메라는 농장의 사진을 찍어 자동으로 젖소들의 위치를 파악해 준다. 하지만, 위치 추적 알고리즘이 그렇게 썩 좋지는 않기 때문에 더 좋은 방법을 만들어내야 한다.

카메라로 촬영한 농장 사진은 n*n 크기의 문자 배열 형태로 표현되며, 각 문자들은 26가지의 색을 A ~ Z 문자로 표현한다. 존은 다음과 같은 방법으로 소들이 있을 가능성이 있는, 잠재적 젖소 위치(PCL)를 다음과 같이 판단한다.:

PCL 은 사각형 모양이다. 이미지 전체가 될 수도 있고, 가로와 세로로 잘라서 더 작은 사각형으로 만들 수 있다.
PCL은 다음과 특징을 가져야 한다.:
- 그 사각형으로 조각만 생각하고, 나머지 부분은 고려하지 않는다.
- 2개의 색으로만 구성되어야 한다. 어떤 색으로는 한 덩어리로 모두 연결되어있고, 다른 색으로는 2개 이상의 부분으로 분리되어 있다.
단, 어떤 PCL 에 포함되는 사격형은 위의 조건을 만족하더라도 PCL로 카운트 하지 않는다.

예를 들어, 다음과 같이 표현된 사진

AAAAA
ABABA
AAABB

는 PCL 일 수 있다. 왜냐하면 A는 하나로 연결된 지역이고, B는 여러 개로 나뉘어진 덩어리 지역으로 볼 수 있기 때문이다. 이를 해석하면, A는 소들로 판단하고, B는 일반 땅이라고 판별할 수 있다. 연결된 지역의 의미는 위, 아래, 왼쪽 오른쪽으로 인접해서 같은 색으로 되어있어 이동할 수 있다는 것을 의미한다.

카메라 데이터가 주어질 때, 이미지에 들어있는 PCL 조각의 개수를 출력해보자.

Input

첫 번째 줄에는 사진의 크기(n)가 입력된다.(1 <= n <= 20)
그 다음 n개의 줄에는 사진 데이터가 입력된다.

Output

만들 수 있는 PCL 조각의 개수를 출력한다.

IO Example

입력1
4
ABBC
BBBC
AABB
ABBC

출력1
2


예시 데이터는 2개의 PCL 조각이 있다.
ABB
BBB
AAB
ABB

BC
BC
BB
BC


입력2
5
CCCCC
CABAC
CABAC
CABAC
CCCCC

출력2
4


예시 데이터는 4개의 PCL 조각이 있다.

C
A
A
A
C

C
B
B
B
C

C
A
A
A
C

ABA
ABA
ABA

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]